[FOM] 2,3 Turing machine proof controversy

[Alex Galicki]

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?


regards,
Alex