Darren New schrieb:

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

Provided that you have a "homogenous" initial state except for a "local 
anomaly" (as is the case for a TM), I'm pretty sure that you cannot only 
/begin/ to simulate that, but even /continue/ to do so, with no more or 
less memory requirements than for a TM.

I reckon that if the whole smash /starts/ with a local anomaly, some 
repeating pattern to the "left" and some (possibly different) repeating 
pattern to the "right", the next step will again leave a local anomaly 
with a pattern to the left and right, except that the patterns may have 
a significantly longer period, and the local anomaly may have grown.

So "all" you have to do is simulate the local anomaly, as well as the 
repeating pattern.

Even if you "duplicate" the anomaly at regular intervals, all this will 
do is change the repeating pattern.

Thus, I still see no fundamental difference.

Sure, I do see why an actual /implementation/ (as opposed to mere 
simulation) of such a machine would be infeasible for /different/ 
reasons than a TM, but I wouldn't attribute this to the /tape/ being 
infinite vs. just "unbounded", but rather the rules in this case 
allowing to /access/ an infinitely large number of cells in a /single/ step.


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

See above for how I'd try to approach this. If it has any repeating 
pattern, you don't need infinite storage to represent it.

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

You still haven't managed to come up with any, from what I see.

Post a reply to this message