The Rule 30 prize problems are three questions about the central column of rule 30 started from a single black cell on an otherwise white infinite line. Wolfram (2019) announced a prize of $10,000 for the resolution of each question.
Let 
be 1 if the central cell is black after 
steps and 0 otherwise, so 
. The questions are
1. Is the sequence 
not eventually periodic?
2. Do black and white cells have equal limiting frequencies in the central column, that is, does the limit satisfy
 |
3. Does computing 
necessarily require at least linear computation time
in 
?
The third question concerns computational irreducibility. Jen's (1990) result for two adjacent cells does not establish the corresponding claim for the central column alone.
