clipka wrote:
> They may be /isomorphic/, but still they're different.

That would be "equivalent" then.

> I've never heard of "single-ended tape" Turing machines except as a 
> special case.

It's not too common, because it's unnecessary, and it adds no power to the 
descriptive system. Normally if you try to go left from the first position, 
that's a halting state.

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

Feel free. Math doesn't care whether you agree or not.

> It is irrelevant whether a Turing machine uses an /infinite/ tape, or 
> just has its tape /extended/ as needed: 

No, really, it truly and deeply isn't the same thing.

Look, I'm going to build a cellular automata. It's going to have one rule.

"Look at all positions to the right of the cell. If anywhere in there there 
are exactly 20 black cells with at least one white cell on either side, make 
this cell black."

That's an infinite tape description. You *cannot* even *begin* to simulate 
that on *any* computer. It's more than what a TM can compute.

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

Here's a pseudo-Turing machine:

"State one: write a 1 to every odd-numbered tape entry, then go to state 2"
"State two: write a 2 to every even-numbered tape entry, then halt."

That halts in 3 steps or less (depending how you count). Code that up in a 
Turing machine with merely bounded tape.

> cannot theoretically be refuted, but it's plain good old nonsense 
> practically.

Not really. You build more and more tape as time goes on. But again, of 
course, you're arguing that real physical computers can't run forever. Yes, 
sure, granted. But irrelevant.

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

See above. We have abstractions which *are* infinite and which you *cannot* 
calculate with a turing machine.

> I also fail to see any theoretical difference between an infinite tape, 
> and a tape being grown automatically as needed.

See above. A UTM cannot quantify over the contents of the tape. This puts 
whole boatloads of things that can be described outside the realm of 
"calculation".

-- 
   Darren New, San Diego CA, USA (PST)
   I ordered stamps from Zazzle that read "Place Stamp Here".

Post a reply to this message