[FOM] Simple Turing machines, Universality, Encodings, etc.
Todd Rowland
rowland at wolfram.com
Wed Oct 31 21:49:24 EDT 2007
On Tue, 30 Oct 2007, Rob van Glabbeek wrote:
> Claim 1: The following construction of a non-periodic semi-infinite
> tape is similar in spirit to Smith's.
>
> Take universal Turing machine U. We are going to write a
> right-infinite tape by traversing once from left to right.
> By means of any standard function f embedding NxN in N, we enumerate
> all pairs (i,t) in NxN and let U run for t steps on input i.
> Here input strings of U are seen as integers i in a standard way.
> If U halts, we write the number i in unary as i a's,
> followed by a b. Otherwise, we write i+1 dummy symbols d.
>
Embedding an oracle in the intial conditions is clearly far beyond what is
allowed. Not to mention that one would not be able to write a program
which will succeed in writing these initial conditions. If you are going
to make a procedure for producing initial conditions in the spirit of
Smith's construction, then part of that is that it must be computable.
More information about the FOM
mailing list