[FOM] 2,3 Turing machine proof controversy

[Alexander Smith]

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
trivial.

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
        halt
     end
end


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

Would it be

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

Or

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

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