[FOM] 2,3 Turing machine proof controversy
Alex Galicki
alex.galicki at googlemail.com
Fri Nov 9 02:59:21 EST 2007
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
More information about the FOM
mailing list