Goldbach's conjecture
A 748-state binary Turing machine has been constructed that halts iff ZFC is inconsistent. A 744-state Turing machine has been constructed that halts iff the Riemann hypothesis is false. A 43-state Turing machine has been constructed that halts iff Goldbach's conjecture is false, and a 27-state machine for that conjecture has been proposed but not yet verified.