PPL 141 / 177 permanent IDsPrize Problem Ledger · PPLChecked 2026.07.27
Prize Problem LedgerWolfram Rule 30 prizesPPL 141Rule 30 computational irreducibility

Permanent problem IDPPL 141

Verified openIndependentconjecture

Cellular automata

Rule 30 computational irreducibility

Prove or disprove that computing the nth center-column cell of Rule 30 necessarily requires at least order-n computational effort.

Rule 30dynamical systemscomputational complexity
01

The problem

Prove or disprove that computing the nth center-column cell of Rule 30 necessarily requires at least order-n computational effort.

Open since2019prize launch
Last checked2026.07.27Catalog verification
02

Reward offers

Offer 01$10,000Stephen Wolfram / Wolfram Research
Documented

The first correct full proof wins. Submissions may be by an individual or group and must be original work presented in a paper suitable for publication; the prize committee’s decision is final.

03

Sources & reading