Idk other automaton forum so I post in here,this may be out of topic because the other cellular automaton section is within game of life section but maybe because it's cellular automaton forum so there's people that know automaton rule 30
In this text I want to share the shortcut or method to calculate automaton rule 30 center digit,so this text solve problem 3,"Does computing the nth cell of the center column require at least O(n) computational effort?",because it's shortcut so the answer is no,to calculate 275th row center digit(which is example in this text) you don't need 275 steps so it's not at least 0(n)
affection definition:
change the comparison variable,x≥y→y≥x
affection rule:
if there's digit 1 next to digit 1 then do affection
if there's digit 1 in left side then do affection
If theres non zero digit in section then do affection in the section comparison(hard to explain but there's example in 12 digit calculation)
the more the rule apply the more affection
step:
-convert the n to binary(1=00000001
-separate to 4 digit each(00000000→0000 0001)
-put total digit÷4 variable for 4 digit each(y=0001)
-map the position and value,0001{4,3,2,1}="1"=1,"0"=4+3+2=9
-compare,first digit≥other digit,in 0001 case because the first digit is 0 so it's "0"≥"1"=9≥1=correct=1
-if there's affection reaction then flip,exception for affection because left section is not zero is do the affection in the comparison
example:
3rd center digit:
00000011→0000 0011
x=0000 y=0011
because there's no non zero in x so we can skip it
0011{4,3,2,1}="1"=1+2=3,"0"=4+3=7
because 0 is the first digit so it's "0"≥"1" but because there's digit 1 next to other digit 1 so there's affection
"0"≥"1"→"1"≥"0"
3≥7=incorrect=0 so 3rd row center digit is 0
275th center digit:
275=101010100001→1010 1010 00001
12 digits÷4=3 so there's 3 variables
x=1010,y=1010,z=0001
1010{4,3,2,1}="1"=4+2,"0"=3+2=5
because the first digit is 1 so it's "1"≥"0" but there's digit 1 in left side so there's affection,"1"≥"0"→"0"≥"1"=5≥4+2=incorrect=0
because the y digit is same as x we can skip it
0001{4,3,2,1}="1"=1,"0"=4+3+2=9
because the first digit is 0 so it's "0"≥"1"=9≥1=correct=1
so the result is x=0,y=0,z=1,then compare
because theres non zero digit in section x&y so there's 2 times affection
x≥y≥z
x≥y≥z→y≥x≥z→y≥z≥x
(y≥z)≥x
(0≥1)≥0
0≥1=incorrect=0
0≥0=correct(0=0)=1 so for 275th row the center digit is 1