 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New schrieb:
> I understand that and I agree. My sole point originally was to say that
> it's not a logical implication that "hardwired" implies "not turing
> complete".
It does, when the context implies that "hardwired" means that an option
to re-program /without/ re-wiring does /not/ exist, regardless how you
wire it.
> If you go back to what I originally wrote:
>
> """
> > - Even its 1943 successor, "Colossus", was not Turing-complete, and
> programmable only by re-wiring.
>
> Just to avoid confusion, everyone should be aware that Turing machines
> are programmable only by re-wiring. Those two clauses have nothing to do
> with each other. :-)
> """
>
> You can see that I'm saying that just because you need to change wiring
> to program something doesn't keep it from being turing complete. The
> converse isn't addressed.
If "you /need/ to change wiring to program something" (emphasis added),
then it /does/ keep it from being turing complete.
If the machine is capable of being wired to be Turing complete
(accepting "soft-programming"), then you possibly don't /need/ to change
wiring, as it /may/ happen to already be wired just the way you need.
>> And by virtue of being a UTM, it is automatically "soft-programmable"
>> as well.
>
> Sort of, yes. (Sort of in the sense that a UTM interpreting its tape is
> isomorphic to the actual turing machine being interpreted, but not
> identical to it.)
This is the /only/ sense in which the term "soft-programmable" can be
interpreted without becoming pure nonsense - whether it is a UTM or any
other computing device - so I'm taking this interpetation for granted.
It doesn't matter whether the UTM is just /isomorphic/ to some TM it
simulates: The system as a whole runs a /program/, part of which is
stored on the tape.
> I think you're arguing against a statement I haven't made. I was simply
> pointing out to whoever might not know it that just because a computer
> needs to be physically modified to run a different program doesn't mean
> it isn't Turing complete.
And it is exactly /this/ statement I'm arguing against. It is a
statement about a computer with a certain /requirement/ regarding
programming. If a computer /has/ that requirement (and not just an
/option/ to that effect), it /does/ mean it isn't Turing complete, and
therefore your statement is simply false.
>> There is, however, no way to build a UTM that, at /every/ level, can
>> read program logic from ROM /only/.
>
> That *is* what a Turing machine does. There's no code on the tape that
> executes. That's the whole *point* of defining a UTM - that there is a
> program that can simulate running any other TM hardware program.
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.
I therefore argue that this low-level perspective is pure nonsense in
this discussion.
>> It must be "soft-programmable" at /some/ level in order to qualify as
>> Turing-complete.
>
> Great. Now define the words you put in quotes precisely and mathematically.
I'm not going to that level, because I'm not a mathematician, and
therefore leave its definition to common sense.
> Well.... The barrier to being Turing complete is amazingly low. If you
> have anything remotely close to a Turing machine, then it's going to be
> Turing compatible.
No, it's not automatically going to be: It depends on the "wiring"; for
instance, a Turing machine constituting a Busy Beaver will never be
Turing complete, despite /being/ a Turing machine (which should qualify
as "anything remotely close" in this sense I guess).
I cannot help but note that for someone demanding from /me/ precise
mathematical definitions, you're surprisingly lax in your own wording.
> It takes less than 30 states and one read/write cycle
> on one symbol of a tape-like memory to qualify.
To avoid confusion, I take the "one symbol" to mean "one symbol plus the
empty-cell symbol" (which I as a layman would consider a total of two
symbols).
> But if you can write to and read from memory, make a decision, and
> branch to a different place in the ROM based on that memory, you're
> Turing complete. Heck, you can be Turing complete if you have just one
> instruction.
Just one instruction at what abstraction level? CPU? Or "bytecode" (or
"soft-programming" to stick to my original term) interpreted by jumping
around in the ROM?
(And again: No, just the mentioned abilities does not /necessarily/ make
your machine Turing complete. It only enables you to simulate /some/
Turing machine(s) - only the proper ROM content would make it Turing
complete, so your ability to /make/ the machine Turing complete would
depend on what part of the ROM you could re-program - or "re-wire", if
you like.)
> I think we're agreeing, but I think you're ascribing to me at least one
> position I never took.
It may be a position you never /intended/ to take, but you persistently
keep taking by your choice of words, so it's hard for me to tell.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
clipka wrote:
> Darren New schrieb:
>
>> I understand that and I agree. My sole point originally was to say
>> that it's not a logical implication that "hardwired" implies "not
>> turing complete".
>
> It does, when the context implies that "hardwired" means that an option
> to re-program /without/ re-wiring does /not/ exist, regardless how you
> wire it.
You understand that Turing machines are hard-wired, right? You can't
reprogram them without rewiring them?
> If "you /need/ to change wiring to program something" (emphasis added),
> then it /does/ keep it from being turing complete.
I suspose it's arguing over what "programming" means, now.
> If the machine is capable of being wired to be Turing complete
> (accepting "soft-programming"), then you possibly don't /need/ to change
> wiring, as it /may/ happen to already be wired just the way you need.
If you're talking about real machines with real I/O and such, then no, maybe
you want to rewire it anyway.
>>> And by virtue of being a UTM, it is automatically "soft-programmable"
>>> as well.
>>
>> Sort of, yes. (Sort of in the sense that a UTM interpreting its tape
>> is isomorphic to the actual turing machine being interpreted, but not
>> identical to it.)
>
> This is the /only/ sense in which the term "soft-programmable" can be
> interpreted without becoming pure nonsense - whether it is a UTM or any
> other computing device - so I'm taking this interpetation for granted.
>
> It doesn't matter whether the UTM is just /isomorphic/ to some TM it
> simulates: The system as a whole runs a /program/, part of which is
> stored on the tape.
Yes, but the output of that program might not appear anywhere on the tape.
If I take a Turing machine to add two numbers together from the tape and
write the result on the tape, there's nothing that says a UTM running that
program will read two numbers off the tape and write the result on the tape.
>> I think you're arguing against a statement I haven't made. I was
>> simply pointing out to whoever might not know it that just because a
>> computer needs to be physically modified to run a different program
>> doesn't mean it isn't Turing complete.
>
> And it is exactly /this/ statement I'm arguing against. It is a
> statement about a computer with a certain /requirement/ regarding
> programming. If a computer /has/ that requirement (and not just an
> /option/ to that effect), it /does/ mean it isn't Turing complete, and
> therefore your statement is simply false.
Alright, so you're arguing over the word "is". Fair enough. You're saying
that your statement "has to be rewired" is to be interpreted as logically
implying it's incapable of being rewired into a universal machine.
I don't agree that most people interested in the subject would interpret
your sentence that way, but if you do, sure, you've defined your statement
to mean that, so there ya go.
I would have said "if it can't be rewired into a universal machine, then you
have to rewire it for every calculation."
>> That *is* what a Turing machine does. There's no code on the tape that
>> executes. That's the whole *point* of defining a UTM - that there is a
>> program that can simulate running any other TM hardware program.
>
> 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.
> I therefore argue that this low-level perspective is pure nonsense in
> this discussion.
I disagree.
>>> It must be "soft-programmable" at /some/ level in order to qualify as
>>> Turing-complete.
>>
>> Great. Now define the words you put in quotes precisely and
>> mathematically.
>
> I'm not going to that level, because I'm not a mathematician, and
> therefore leave its definition to common sense.
Well, that's exactly what Turing did, which is why he's still world famous. :-)
>> Well.... The barrier to being Turing complete is amazingly low. If you
>> have anything remotely close to a Turing machine, then it's going to
>> be Turing compatible.
>
> No, it's not automatically going to be: It depends on the "wiring"; for
> instance, a Turing machine constituting a Busy Beaver will never be
> Turing complete, despite /being/ a Turing machine (which should qualify
> as "anything remotely close" in this sense I guess).
Fair enough. Obviously I meant to say if you have something remotely close
to being a turing machine which you can rewire the state machine of.
> I cannot help but note that for someone demanding from /me/ precise
> mathematical definitions, you're surprisingly lax in your own wording.
You're taking this way too seriously. You can win.
> > It takes less than 30 states and one read/write cycle
>> on one symbol of a tape-like memory to qualify.
>
> To avoid confusion, I take the "one symbol" to mean "one symbol plus the
> empty-cell symbol" (which I as a layman would consider a total of two
> symbols).
No. One symbol is what's stored on one position the tape, which may be more
than one bit. I think the minimum turing machine is 28 states and 3 baud or
something.
>> But if you can write to and read from memory, make a decision, and
>> branch to a different place in the ROM based on that memory, you're
>> Turing complete. Heck, you can be Turing complete if you have just one
>> instruction.
>
> Just one instruction at what abstraction level? CPU?
CPU. I.e., the hardware only interprets one opcode.
> Or "bytecode" (or
> "soft-programming" to stick to my original term) interpreted by jumping
> around in the ROM?
> (And again: No, just the mentioned abilities does not /necessarily/ make
> your machine Turing complete. It only enables you to simulate /some/
> Turing machine(s) - only the proper ROM content would make it Turing
> complete, so your ability to /make/ the machine Turing complete would
> depend on what part of the ROM you could re-program - or "re-wire", if
> you like.)
There's no ROM. There's just one instruction reading data out of the memory.
>> I think we're agreeing, but I think you're ascribing to me at least
>> one position I never took.
>
> It may be a position you never /intended/ to take, but you persistently
> keep taking by your choice of words, so it's hard for me to tell.
You're making ambiguous statements (as am I, by the very nature of language)
which we're interpreting differently, is all.
--
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:
> 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
|
|
| |
| |
|
|
|
|
| |
|
|
