|
|
clipka wrote:
> Erm... do you /really/ know what you're talking about?
Yes.
> Whenever a Turing machine's tape is defined as having /any/ end at all,
> then it is defined as having /two/ ends, /both/ of which will be
> automatically extended as needed.
There are lots of definitions of Turing machines. Some have one end, some
have no ends. They're all equivalent, mathematically.
> But I prefer to stick to Turing's own description:
>
> "...an infinite memory capacity obtained in the form of an /infinite
> tape/..." (Turing 1948, p. 61)
>
>
> There. Emphasis added. Any further questions?
Well, he's wrong. :-)
> (Yes, there /are/ variations on the theme that use a tape which is
> bounded in /one/ direction only; these are, however, not classic generic
> Turing machines.)
Whatever.
No Turing machine has or needs an infinite tape, unless you want to
initialize an infinite length of tape with some pattern of symbols.
Do you understand why Turing machines have an unbounded tape while (say)
linear cellular automata have infinite tapes?
No matter how long a Turing machine runs, it cannot access an infinite
amount of tape. Therefore, the tape needn't be infinite, merely unbounded,
and that's a *huge* difference.
--
Darren New, San Diego CA, USA (PST)
I ordered stamps from Zazzle that read "Place Stamp Here".
Post a reply to this message
|
|