PPL 145 / 177 permanent IDsPrize Problem Ledger · PPLChecked 2026.07.26
Prize Problem LedgerIndependentPPL 145Shallit #13 · Prime acceptance by an automaton

Permanent problem IDPPL 145

Source-statedIndependentconjecture

Formal languages

Shallit #13 · Prime acceptance by an automaton

Is it decidable whether a given base-k DFA accepts the representation of at least one prime number?

automata theorytheoretical computer scienceformal languages
01

The problem

Is it decidable whether a given base-k DFA accepts the representation of at least one prime number?

Open since2014source-stated by 2014
Last checked2026.07.26Catalog verification
02

Reward offers

Offer 01£50Jeffrey Shallit
Personal offer

Personal cash offer stated in Shallit’s official talk. The live talks page records subsequent updates, including a paid solution to one omitted problem; confirm claim procedure with the sponsor before relying on the award.

03

Sources & reading