 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New schrieb:
> Having the program in hard wiring doesn't make it impossible to be
> Turing complete. *That* is what I was arguing.
If a machine can only be programmed by hard wiring, and none of the hard
wiring options implements a capability for soft programming, then it
/is/ impossible to be Turing complete. That is what /I/ was arguing.
>> I'm perfectly aware of that. But it is a misconception to think that
>> the architecture of a computing device must necessarily be akin to
>> that of a Turing machine.
>
> Huh? When did I ever say anything close to that?
>
> All I asserted was that "reprogramming requires rewiring" is orthogonal
> to "is not Turing complete." At *some* level of abstraction, every
> computer requires rewiring in order to reprogram it.
You did, as a matter of fact, assert that Colossus could have been
hard-wired into a UTM, provided it had enough cables to re-wire.
Aside from that: Yes, any soft-programmable machine - including (but not
limited to) any such Turing machine - does have a hard-wired programming
at its core, so /any/ computing device can be reprogrammed by re-wiring.
However, if a device's hard-programming does not (and cannot) provide
for any means to program it at a non-hardware level, that /is/ contrary
to being Turing complete: a UTM, by definition, reads the details of the
Turing machine to simulate (viz: the program) from its tape, i.e. the
program is part of the data it works on. To simulate a UTM, you need to
simulate this aspect as well, therefore being Turing complete /requires/
the ability to be re-programmable without re-wiring (at least in /some/
wiring configuration).
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp schrieb:
> clipka <ano### [at] anonymous org> wrote:
>> Darren New schrieb:
>>> clipka wrote:
>>>
>>> > as it requires an infinitely long memory tape
>>>
>>> No it doesn't. It only requires an unbounded memory tape. There's a huge
>>> difference.
>
>> There is a huge difference indeed, and that's why you're mistaken. A
>> loop of memory tape would also fit the bill of "unbounded"; however, it
>> doesn't do for a true Turing machine.
>
> A loop of memory tape does not, in fact, provide an unbounded amount
> of memory. It provides a finite, fixed amount of memory, hence very
> definitely not unbounded.
Note that there is a difference between an "unbounded amount of memory",
and an "unbounded memory tape": In the former case we're talking about
an absence of limit in quantity, in the latter we're talking about a
topological property.
Note that I'm interpreting the grammatical construct "unbounded memory
tape" to read "unbounded thing called a memory tape", not "tape
constituting an unbounded [amount of] memory"; your interpretation may
differ.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
clipka wrote:
> Darren New schrieb:
>
>> Yes. Unbounded amounts of storage, not infinite amounts of storage.
>> It's not difficult to arrange for a Turing machine to access however
>> much memory it needs.
>
> Consider a Turing machine that does not halt, but keeps advancing on the
> tape.
>
> There. Arrange for *that* to access however much memory it needs. It is
> /not/ physically possible.
Yes. That doesn't make it infinite. You can arrange for that by making the
speed of the machine 1/2^N where N is the number of slots filled in the tape.
You can't do that with something that needs an infinite amount of tape.
Sure, I was unclear. You can't arrange for *every* machine to have as much
tape as it needs. But you *can* arrange for *some* machines to have as much
tape as they need, which is *not* the case for a programming paradigm that
requires an infinite amount of storage. Most of the practically interesting
machines do *not* consume unlimited amounts of memory before they halt.
--
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:
> Darren New schrieb:
>
>> Having the program in hard wiring doesn't make it impossible to be
>> Turing complete. *That* is what I was arguing.
>
> If a machine can only be programmed by hard wiring, and none of the hard
> wiring options implements a capability for soft programming, then it
> /is/ impossible to be Turing complete. That is what /I/ was arguing.
Fair enough. I was just disputing the version of that without the "none of
the hard wiring options implements a capability for soft programming" part,
which is how you seemed to be phrasing it at the start.
>> All I asserted was that "reprogramming requires rewiring" is
>> orthogonal to "is not Turing complete." At *some* level of
>> abstraction, every computer requires rewiring in order to reprogram it.
>
> You did, as a matter of fact, assert that Colossus could have been
> hard-wired into a UTM, provided it had enough cables to re-wire.
Yes. Clearly, it needs to have enough hard-wiring operations to be able to
operate on arbitrary memory and so on. A differential engine isn't going to
be Turing complete.
> Aside from that: Yes, any soft-programmable machine - including (but not
> limited to) any such Turing machine - does have a hard-wired programming
> at its core, so /any/ computing device can be reprogrammed by re-wiring.
That's not what I meant. I meant that at some level of detail, *every*
computing device must be reprogrammed by re-wiring. If you want a different
instruction set, you need to change the CPU. If your CPU is microcoded, you
need to change the CPU to use a different type of microcode. Etc.
> However, if a device's hard-programming does not (and cannot) provide
> for any means to program it at a non-hardware level, that /is/ contrary
> to being Turing complete:
All you need is to hard-wire the machine to be a UTM. If you have enough
read/write storage and a state machine, you're Turing complete. It doesn't
even take a big state machine. (Something like 3 states with 5 symbols, or 5
states of 3 colors, or something like that.)
> a UTM, by definition, reads the details of the
> Turing machine to simulate (viz: the program) from its tape, i.e. the
> program is part of the data it works on.
Yes.
> To simulate a UTM, you need to simulate this aspect as well,
Yes.
> therefore being Turing complete /requires/
> the ability to be re-programmable without re-wiring (at least in /some/
> wiring configuration).
Certainly not every hard-wired program is Turing complete, if that's what
you're implying. A hard-wired program to divide two numbers in memory isn't
going to give you a Turing complete machine. If you hard-wire the machine to
read the TM state table off the start of the input and follow the rules in
it, then you have a hard-wired universal turing machine.
Being Turing complete doesn't require the UTM to change its program without
rewiring, any more than having microcode requires the ability to rewire the
CPU at runtime.
I think it's just a confusion that you're mixing up too many levels at once.
A Universal Turing Machine doesn't change its hard-wiring to simulate other
Turing machines. It gets fed the descriptions of hardware via its inputs,
but the UTM itself has exactly one program it runs. Put it this way: there's
nothing that prevents you from building a UTM whose program logic can only
be read from ROM and not RAM.
--
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:
> Note that I'm interpreting the grammatical construct "unbounded memory
> tape" to read "unbounded thing called a memory tape", not "tape
> constituting an unbounded [amount of] memory"; your interpretation may
> differ.
Given the mathematical definition of the memory tape in a TM, this
interpretation makes no sense. Everyone says "unbounded tape" because that
implies "unbounded amount of storage" given how the tape is defined. (I.e.,
it's defined as having one end as well as operations to move left and right.)
--
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:
> There. Arrange for *that* to access however much memory it needs. It is
> /not/ physically possible.
BTW, this has nothing to do with whether you can have a hard-wired UTM. All
this means is that no real physical computer or simulated computer can ever
actually be a Turing machine at all. But we knew that. :-)
--
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:
>> Aside from that: Yes, any soft-programmable machine - including (but
>> not limited to) any such Turing machine - does have a hard-wired
>> programming at its core, so /any/ computing device can be reprogrammed
>> by re-wiring.
>
> That's not what I meant. I meant that at some level of detail, *every*
> computing device must be reprogrammed by re-wiring. If you want a
> different instruction set, you need to change the CPU. If your CPU is
> microcoded, you need to change the CPU to use a different type of
> microcode. Etc.
What I mean is that at every computing device /can/ be reprogrammed by
re-wiring; but note that this is no /must/: I can happily live without
re-wiring my Intel i7 machine, knowing that it is /pre-wired/ to be
Turing-complete already :-) (within memory constraints of course).
>> However, if a device's hard-programming does not (and cannot) provide
>> for any means to program it at a non-hardware level, that /is/
>> contrary to being Turing complete:
>
> All you need is to hard-wire the machine to be a UTM.
And here's where I need to repeat myself: There are machines you
/cannot/ possibly hard-wire to be a UTM.
/If/ a machine can be hard-wired that way, then this /implies/ (and
therefore also, in terms of logic, /requires/) that the device /can/
provide for a means to program it at a non-hardware level - because that
is a key feature of /any/ UTM.
So I repeat again: If a device's hard-programming /can not/ provide for
any means to program it at a non-hardware level (even with the most
clever hard-wiring option), that /is/ contrary to being Turing complete.
> If you
> hard-wire the machine to read the TM state table off the start of the
> input and follow the rules in it, then you have a hard-wired universal
> turing machine.
Well, what this gives you is no more and no less than /a universal
Turing machine/, which /by definition/ of a Turing machine is hard-wired.
And by virtue of being a UTM, it is automatically "soft-programmable" as
well.
> Being Turing complete doesn't require the UTM to change its program
> without rewiring, any more than having microcode requires the ability to
> rewire the CPU at runtime.
A UTM is /always/ Turing complete by definition. And while it doesn't
require its /own/ program to be modifiable without re-wiring, it
/implies/ that the program /to simulate/ be modifiable without.
Therefore, to be Turing complete by definition /implies/ (and therefore,
in terms of logic, /requires/) that the machine - whether it be an
actual UTM or some other device capable of simulating a UTM - be
re-programmable without re-wiring at /some/ level.
> I think it's just a confusion that you're mixing up too many levels at
> once.
No, I'm pretty sure I'm not mixing them up. Though you may not be aware
of the fact that my initial argument covers /all/ those levels.
> A Universal Turing Machine doesn't change its hard-wiring to
> simulate other Turing machines. It gets fed the descriptions of hardware
> via its inputs, but the UTM itself has exactly one program it runs. Put
> it this way: there's nothing that prevents you from building a UTM whose
> program logic can only be read from ROM and not RAM.
There is, however, no way to build a UTM that, at /every/ level, can
read program logic from ROM /only/.
It must be "soft-programmable" at /some/ level in order to qualify as
Turing-complete.
Therefore, I repeat my initial argument: A machine that can /only/ be
programmed by re-wiring (i.e. provides /no/ abstraction level whatsoever
at which it can be programmed otherwise) /cannot/ be Turing complete.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New schrieb:
> clipka wrote:
>> Note that I'm interpreting the grammatical construct "unbounded memory
>> tape" to read "unbounded thing called a memory tape", not "tape
>> constituting an unbounded [amount of] memory"; your interpretation may
>> differ.
>
> Given the mathematical definition of the memory tape in a TM, this
> interpretation makes no sense. Everyone says "unbounded tape" because
> that implies "unbounded amount of storage" given how the tape is
> defined. (I.e., it's defined as having one end as well as operations to
> move left and right.)
Erm... do you /really/ know what you're talking about?
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.
But I prefer to stick to Turing's own description:
"...an infinite memory capacity obtained in the form of an /infinite
tape/..." (Turing 1948, p. 61)
There. Emphasis added. Any further questions?
(Yes, there /are/ variations on the theme that use a tape which is
bounded in /one/ direction only; these are, however, not classic generic
Turing machines.)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
clipka wrote:
> Darren New schrieb:
>
>>> Aside from that: Yes, any soft-programmable machine - including (but
>>> not limited to) any such Turing machine - does have a hard-wired
>>> programming at its core, so /any/ computing device can be
>>> reprogrammed by re-wiring.
>>
>> That's not what I meant. I meant that at some level of detail, *every*
>> computing device must be reprogrammed by re-wiring. If you want a
>> different instruction set, you need to change the CPU. If your CPU is
>> microcoded, you need to change the CPU to use a different type of
>> microcode. Etc.
>
> What I mean is that at every computing device /can/ be reprogrammed by
> re-wiring; but note that this is no /must/: I can happily live without
> re-wiring my Intel i7 machine, knowing that it is /pre-wired/ to be
> Turing-complete already :-) (within memory constraints of course).
Sure. If you want your Intel to run a different instruction set, you need to
rewire it. If the instruction set is powerful enough for your needs, you
don't need to do that.
>>> However, if a device's hard-programming does not (and cannot) provide
>>> for any means to program it at a non-hardware level, that /is/
>>> contrary to being Turing complete:
>>
>> All you need is to hard-wire the machine to be a UTM.
>
> And here's where I need to repeat myself: There are machines you
> /cannot/ possibly hard-wire to be a UTM.
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".
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.
> So I repeat again: If a device's hard-programming /can not/ provide for
> any means to program it at a non-hardware level (even with the most
> clever hard-wiring option), that /is/ contrary to being Turing complete.
Yes. But it's not just the hard wiring that causes it, but rather the
structure of the machine interpreting the "hard wires".
> > If you
>> hard-wire the machine to read the TM state table off the start of the
>> input and follow the rules in it, then you have a hard-wired universal
>> turing machine.
>
> Well, what this gives you is no more and no less than /a universal
> Turing machine/, which /by definition/ of a Turing machine is hard-wired.
Yes.
> 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.)
>> Being Turing complete doesn't require the UTM to change its program
>> without rewiring, any more than having microcode requires the ability
>> to rewire the CPU at runtime.
>
> A UTM is /always/ Turing complete by definition. And while it doesn't
> require its /own/ program to be modifiable without re-wiring, it
> /implies/ that the program /to simulate/ be modifiable without.
Yes.
> Therefore, to be Turing complete by definition /implies/ (and therefore,
> in terms of logic, /requires/) that the machine - whether it be an
> actual UTM or some other device capable of simulating a UTM - be
> re-programmable without re-wiring at /some/ level.
Yes. Now here's the "some level" part: It takes something external to the TM
to decide what the bits of the tape *mean*. The UTM's tape is isomorpic to
the TM being simulated, but that's not quite the same as running the TM's
program.
> No, I'm pretty sure I'm not mixing them up. Though you may not be aware
> of the fact that my initial argument covers /all/ those levels.
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.
> 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.
The point is that even if you only *execute* from ROM, you *can* calculate
every function you *could* calculate by rewiring the machine, *if* your ROM
has the right program in it.
> 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.
> Therefore, I repeat my initial argument: A machine that can /only/ be
> programmed by re-wiring (i.e. provides /no/ abstraction level whatsoever
> at which it can be programmed otherwise) /cannot/ be Turing complete.
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. It takes less than 30 states and one read/write cycle on one
symbol of a tape-like memory to qualify.
Sure, if you have a differential engine that only calculates one function,
it's only going to calculate one function. But it's not like the machine has
to have an "abstraction level" built in. Normal manipulation of plain old
integer data will do the trick.
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.
I think we're agreeing, but I think you're ascribing to me at least one
position I never took. Also, I think while you're technically correct with
the above statement, it's also worded in a way as to be a tautology as well
as far more restrictive in reality than the statement makes it sound.
--
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:
> Erm... do you /really/ know what you're talking about?
Yes.
> 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.
> But I prefer to stick to Turing's own description:
>
> "...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. :-)
> (Yes, there /are/ variations on the theme that use a tape which is
> bounded in /one/ direction only; these are, however, not classic generic
> Turing machines.)
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.
Do you understand why Turing machines have an unbounded tape while (say)
linear cellular automata have infinite tapes?
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.
--
Darren New, San Diego CA, USA (PST)
I ordered stamps from Zazzle that read "Place Stamp Here".
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|
