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

Rob van Glabbeek rvg at cs.stanford.edu
Thu Nov 1 22:57:29 EDT 2007

Todd Rowland <rowland at wolfram.com> writes:
> 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.

In the mail you respond to I actually did produce a algorithm writing
this initial condition, didn't I?

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

How do you define, for this purpose, whether a non-periodic infinite
string is computable?


More information about the FOM mailing list