[FOM] 2,3 Turing machine proof controversy

Alexander Smith AIS523 at bham.ac.uk
Fri Nov 9 12:25:19 EST 2007

The initial condition should always be infinite whether the problem halts or not. The Turing machine that reads it will itself halt if told to emulate more steps than the cyclic tag system itself can run for before halting. There is no need to determine in advance whether or not the cyclic tag system halts.

Alex Smith


From: fom-bounces at cs.nyu.edu on behalf of Alex Galicki
Sent: Fri 09/11/2007 07:59
To: Foundations of Mathematics
Subject: Re: [FOM] 2,3 Turing machine proof controversy

A. Smith:

> Can this system be universal? Imagine the following input:
> ...__R0110_01X_R0110_01XX_110XX_R0110_01XXX_110XXX_01XXX_R...
> This input tells the system to emulate the cyclic tag system for one
> step, then two steps, then three steps, then so on. The input to this
> system isn't periodic, but is simple to construct in a non-universal
> way. Is this Turing machine universal?

To produce such an initial condition for program P one has to know
upfront if P halts or not. If P halts the condition should be finite,
and if P doesn't halt it should be infinite. So the mechanism
responsible for creating such an initial condition effectively would
have to solve the Halt Problem. I would not call such a mechanism

Consider program searching for a counterexample of the Riemann
hypothesis. Normal program might look like:

for i=1to infinity do:
     if not CheckRiemannHypothesisFor(i) then
        write "Found counterexample:" + i

And how to construct an initial condition of the similar program for
the 2,3 kind of machine without proving or disproving the Riemann

Would it be

_RCheckRiemannHypothesisFor(1)_.....CheckRiemannHypothesisFor(3300044) ?


_RCheckRiemannHypothesisFor(1)_.....CheckRiemannHypothesisFor(99^99) ?

Or maybe the Riemann hypothesis is valid and the initial condition
should be infinite?

More information about the FOM mailing list