 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New schrieb:
>> As mentioned before, in that sense there is /only/ programming through
>> re-wiring, and therefore in that sense it doesn't make sense to even
>> /mention/ such a property for any computing device.
>
> But the whole magic of the property is that you *can* build such an
> interpreter. Before the UTM was invented, it wasn't anyways clear to
> anyone that such a thing was possible. Nobody knew that the rules of
> arithmetic were adequate to express the rules of arithmetic.
True. Yet in 2009, people are taking it for granted by now, so if a
contemporary Wikipedia article claims that Colossus could be
re-programmed "partially (by re-wiring)", then I find it difficult to
imagine that this is to be interpreted anything other than as "partially
(by re-wiring /only/, providing no other option)".
/That/ was the initial starting point of the discussion we're now having.
So in this sense, say: Can a computing machine that is programmable /by
re-wiring only/ ever be Turing complete?
I categorically say no, as there is obviously no way to feed such a
machine with data isomorphic to some generic initial tape content for a
UTM, and have it generate output data isomorphic to what the UTM would
produce.
Unless, of course, you'd consider human "re-wiring operators" as being
part of the machine, and their orders as being part of the input data,
but I guess we agree that this is not normally the scope of how we'd
define a computing device.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
clipka wrote:
> so if a contemporary Wikipedia article claims that Colossus could be re-programmed
"partially (by re-wiring)", then I find it difficult to imagine that this is to be
interpreted anything other than as "partially (by re-wiring /only/, providing no other
option)".
Um, I don't?
> So in this sense, say: Can a computing machine that is programmable /by
> re-wiring only/ ever be Turing complete?
What about a real physical implementation of a Turing machine, where
rewiring it gives you different Turing machines?
True, you have to get the data onto the tape initially, but since that
wouldn't be part of the "program" per se, I don't see where that's addressed.
> but I guess we agree that this is not normally the scope of how we'd
> define a computing device.
Not *now*, no. Back in Turing's day, that's exactly what it was. :-)
--
Darren New, San Diego CA, USA (PST)
I ordered stamps from Zazzle that read "Place Stamp Here".
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
clipka wrote:
> 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.
But *that* is *exactly* the difference between an infinite tape and an
unbounded one. An tape doesn't have to be infinite if you can't access an
infinite number of cells in a finite number of steps. That's exactly 100%
the entire point of the distinction.
> You still haven't managed to come up with any, from what I see.
I'll leave you to look it up in the textbooks, then, if you can't
extrapolate from that to a machine impossible to simulate.
--
Darren New, San Diego CA, USA (PST)
I ordered stamps from Zazzle that read "Place Stamp Here".
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New schrieb:
>> So in this sense, say: Can a computing machine that is programmable
>> /by re-wiring only/ ever be Turing complete?
>
> What about a real physical implementation of a Turing machine, where
> rewiring it gives you different Turing machines?
As I already mentioned, this would require interpreting the "re-wiring
operator" to be considered as part of the Turing machine itself (and the
instructions you give to them as part of the input data), which I would
really hesitate to agree with.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
clipka wrote:
> Darren New schrieb:
>
>>> So in this sense, say: Can a computing machine that is programmable
>>> /by re-wiring only/ ever be Turing complete?
>>
>> What about a real physical implementation of a Turing machine, where
>> rewiring it gives you different Turing machines?
>
> As I already mentioned, this would require interpreting the "re-wiring
> operator" to be considered as part of the Turing machine itself (and the
> instructions you give to them as part of the input data), which I would
> really hesitate to agree with.
I think you're just using "by re-wiring only" to mean "cannot be wired into
a UTM." Which is fine, but an odd kind of interpretation. I don't know the
details of Colossus as such, but it doesn't take a whole lot of wiring to
make a machine that's capable of being a UTM.
--
Darren New, San Diego CA, USA (PST)
I ordered stamps from Zazzle that read "Place Stamp Here".
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|
