[FOM] Simple Turing machines, Universality, Encodings, etc.

[Todd Rowland]

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.