|
![](/i/fill.gif) |
Darren New schrieb:
>> 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.
How can they be equivalent if the resulting pattern on the tape /must/
necessarily be different for some Turing machines (namely those that
also access tape to the left of the starting position)?
They may be /isomorphic/, but still they're different.
I've never heard of "single-ended tape" Turing machines except as a
special case.
>> "...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. :-)
I will not agree with that statement of yours. To me he's right, as he
happens to have invented the concept.
> 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.
Whatever, too.
It is irrelevant whether a Turing machine uses an /infinite/ tape, or
just has its tape /extended/ as needed: Unless you know that the machine
halts and/or enters an infinite loop, there is no way whatsoever to
build a real, reliable TM, because you cannot guarantee that you will be
able to provide for all the tape it may ever need.
And no, I'm not accepting the argument that you can slow down the
machine as its tape grows. That's about the same nonsense argument as
for the race between Achilleus and the Turtle back in ancient Greece: It
cannot theoretically be refuted, but it's plain good old nonsense
practically.
> 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.
However huge that difference may be theoretically, I can't think how
this is of any practical importance for a generic Turing machine with
yet-unknown properties (most particularly a UTM, for that matter).
I also fail to see any theoretical difference between an infinite tape,
and a tape being grown automatically as needed.
Post a reply to this message
|
![](/i/fill.gif) |