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