random

Alex Martelli aleaxit at yahoo.com
Thu Jun 7 18:20:23 CEST 2001


"David C. Ullrich" <ullrich at math.okstate.edu> wrote in message
news:3b1f97ca.4530449 at nntp.sprynet.com...
    ...
> >I think a Universal Turing Machine should by definition
> >accept programs of infinite length.
>
> I don't think that it should. It's supposed to be able to
> "emulate" an arbitrary TM. It takes only finitely much
> space to define a given TM - I don't see any _reason_
> to use infintely much space to hold finitely much data.

I did find a different definition from the Stanford one,
that did include the condition "there can be only finitely
many non-blank squares on the tape" (presumably, although
that wasn't clear to me from that definition, this means
at the START of a run -- if the machine doesn't halt it
may still be allowed to fill the tape with infinitely many
non-blank squares eventually -- but I did not see this
stated unambiguously one way or another).  Not all the
definitions I've found strewn around include this
provision, and it does make a huge difference of course.


Alex






More information about the Python-list mailing list