Re: Smaller UTM than Rule110
Kent Paul Dolan
> are there possible candidates and
> research advances for smaller UTM's
> than Rule110 ?
Probably your question is better directed
to newsgroup comp.theory.cell-automata,
so I've taken the liberty of quoting it
and broadening the distribution.
HTH
xanthian.
[I would be mildly astonished if the answer
to your query were in the affirmative, but
I read these newsgroups to learn, so I'm not
about to prejudge the answer. Though how you
measure "smaller" is going to be an issue;
is Conway's Game of Life "smaller" than
Wolfram's Rule 110, or does being one
dimensional and GoL two dimensional give
Rule 110 an automatic win? You need to
define your metric for your question to
make sense.]
--
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG
Markus Redeker
>"André Betz" <ma...@andrebetz.de> wrote:
>> are there possible candidates and research advances for smaller UTM's
>> than Rule110 ?
>[I would be mildly astonished if the answer to your query were in the
>affirmative, but I read these newsgroups to learn, so I'm not about to
>prejudge the answer. Though how you measure "smaller" is going to be an
>issue; is Conway's Game of Life "smaller" than Wolfram's Rule 110, or does
>being one dimensional and GoL two dimensional give Rule 110 an automatic
>win? You need to define your metric for your question to make sense.]
And then, for rule 110 we don't have a universal Turing machine but a
universal tag system. Which is computational equivalent but not the same.
--
Markus Redeker Hamburg, Germany
Charlie-Boo
> And then, for rule 110 we don't have a universal Turing machine but a
> universal tag system. Which is computational equivalent but not the
same.
I wish people would explain this stuff. If it's "computationally
equivalent", then why isn't it another base of computing (Turing
Complete)? Surely you don't care about the coding.
And how does Rule 110 work (for everyone)?
C-B
Tim Tyler
> >> are there possible candidates and research advances for smaller UTM's
> >> than Rule110 ?
>
> >[I would be mildly astonished if the answer to your query were in the
> >affirmative, but I read these newsgroups to learn, so I'm not about to
> >prejudge the answer. Though how you measure "smaller" is going to be an
> >issue; is Conway's Game of Life "smaller" than Wolfram's Rule 110, or does
> >being one dimensional and GoL two dimensional give Rule 110 an automatic
> >win? You need to define your metric for your question to make sense.]
>
> And then, for rule 110 we don't have a universal Turing machine but a
> universal tag system. Which is computational equivalent but not the same.
This fellow claims to have a program which converts from a TM to a
rule-110 configuration:
[Section entitled: "TuringMachineConverter"]
His own words in an earlier post here were:
``I have written a converter in Java which converts from a Turing Machine
description to CA Rule 110 configuration.''
You can construct Turing machines in any computation-universal space.
--
__________
|im |yler http://timtyler.org/ t...@tt1lock.org Remove lock to reply.
André Betz
> "André Betz" <ma...@andrebetz.de> wrote:
>
>>are there possible candidates and
>>research advances for smaller UTM's
>>than Rule110 ?
Ok I try to explain it a little bit more what I've meant.
Wolfram showed that a simulation of Rule 110 on a TM needs only 5
symbols and 2 states. But he also mentioned that there are smaller UTM
candidates. So my question is, are there any progresses in this case or
are there any groups which work on this case?
Thanks
> [I would be mildly astonished if the answer
> to your query were in the affirmative, but
> I read these newsgroups to learn, so I'm not
> about to prejudge the answer. Though how you
> measure "smaller" is going to be an issue;
> is Conway's Game of Life "smaller" than
> Wolfram's Rule 110, or does being one
> dimensional and GoL two dimensional give
> Rule 110 an automatic win? You need to
> define your metric for your question to
> make sense.]
>
>
--
André Betz
Kontakt: http://www.andrebetz.de/sign.txt
Paul Chapman
> Ok I try to explain it a little bit more what I've meant.
> Wolfram showed that a simulation of Rule 110 on a TM needs only 5
> symbols and 2 states. But he also mentioned that there are smaller UTM
> candidates. So my question is, are there any progresses in this case or
> are there any groups which work on this case?
A Rule 110-based TM is not a true TM, however, for two reasons.
(1) The TM lacks a halt state. In the Rule 110 universal computer, "halt"
is indicated by a certain breakdown in the usual behaviour of the patterns.
(2) The initial tape must be infinite, because the initial Rule 110 pattern
is infinite, ie has an infinite nonblank portion.
This rather limits Rule 110 TMs' uses both for theoretical and practical (!)
purposes. Rule 110 is still universal, provided one has a black box capable
of recognizing the "halt" state. But a TM based upon it is not, because TMs
must halt in a prescribed manner.
Cheers, Paul
Tim Tyler
> > Ok I try to explain it a little bit more what I've meant.
> > Wolfram showed that a simulation of Rule 110 on a TM needs only 5
> > symbols and 2 states. But he also mentioned that there are smaller UTM
> > candidates. So my question is, are there any progresses in this case or
> > are there any groups which work on this case?
>
> A Rule 110-based TM is not a true TM, however, for two reasons.
>
> (1) The TM lacks a halt state. In the Rule 110 universal computer, "halt"
> is indicated by a certain breakdown in the usual behaviour of the patterns.
Turing machines in the real world don't /actully/ come to a halt - in
the sense of the physics of the universe they are ceasing to function.
They merely enter a different state, where they are no longer performing
their usual task.
A Turing machine in a CA can do exactly the same thing.
> (2) The initial tape must be infinite, because the initial Rule 110 pattern
> is infinite, ie has an infinite nonblank portion.
Similarly in the real universe. A Turing machine can't write on empty
space. It needs an infinite writable resource to operate on.
> This rather limits Rule 110 TMs' uses both for theoretical and practical (!)
> purposes. Rule 110 is still universal, provided one has a black box capable
> of recognizing the "halt" state. But a TM based upon it is not, because TMs
> must halt in a prescribed manner.
ISTM that Turing machines in CA universes are no more limited than Turing
machines in the real world are.
Paul Chapman
> > A Rule 110-based TM is not a true TM, however, for two reasons.
> >
> > (1) The TM lacks a halt state. In the Rule 110 universal computer,
"halt"
> > is indicated by a certain breakdown in the usual behaviour of the
patterns.
>
> Turing machines in the real world don't /actully/ come to a halt - in
> the sense of the physics of the universe they are ceasing to function.
>
> They merely enter a different state, where they are no longer performing
> their usual task.
>
> A Turing machine in a CA can do exactly the same thing.
But I was not addressing the "Turing machine in a CA". I was addressing the
same thing as the OP, xanthian and André, which is a TM whose state table is
based on directly simulating a Rule 110 CA, and whose tape contains initial
data representing the pattern of the Rule 110 CA's universe, which in this
case *happens* to contain a pattern which is performing a computation
according to Matthew Cook's design (a "Turing machine in a CA").
The problem is that the state tables of the FSAs at the hearts of these very
small TMs do not contain a halt state. They never halt. A TM which never
halts is not very useful. A TM which never halts certainly cannot qualify
as a UTM.
> > (2) The initial tape must be infinite, because the initial Rule 110
pattern
> > is infinite, ie has an infinite nonblank portion.
>
> Similarly in the real universe. A Turing machine can't write on empty
> space. It needs an infinite writable resource to operate on.
A TM is defined, AFAIK, to have *access* to as long a tape as possible. Any
new tape provided must be blank, ie every cell of the tape must contain a
symbol previously agreed to be the "blank" symbol. (This is an important
theoretical restriction, since it limits the input of a TM to a finite
amount of information.)
We can "simulate" the static state of a TMs tape mathematically (which is a
rather odd way to put it), by describing it as a function f:Z->S, where S is
the symbol set of the TM, and where {i : f{i} ~= "blank"} is finite.
A tape containing a Cook program in a Rule 110 CA has an *infinite* number
of nonblank cells, and therefore is not a TM tape.
> ISTM that Turing machines in CA universes are no more limited than Turing
> machines in the real world are.
Again, we were not talking about TMs in CA universes.
Cheers, Paul
Paul Chapman
I wrote:
> This rather limits Rule 110 TMs' uses both for theoretical and practical
(!)
> purposes. Rule 110 is still universal, provided one has a black box
capable
> of recognizing the "halt" state. But a TM based upon it is not, because
TMs
> must halt in a prescribed manner.
It is of course still possible to build a TM which can simulate the Rule 110
evolution of a cyclic tag system (CTS) emulating a Post tag system emulating
a TM, and which halts when the emulated TM halts. But it would have many
more states than the minimal TM referred to by the OP, since (1) it would
have to simulate the infinite-but-periodic parts of the CA pattern (the
ether at both ends of the CA universe, and the "cyclic" part of the CTS,
which is an infinite number of identical incoming glider salvos on the
right), and (2) it would have to recognize when the CTS had "halted", in
order to halt itself.
Thus Rule 110 remains Turing complete (if Cook's proof is correct :). But
the tiny TMs based on blind simulation of Rule 110 are sadly not universal.
Cheers, Paul
Tim Tyler
> > > A Rule 110-based TM is not a true TM, however, for two reasons.
> > >
> > > (1) The TM lacks a halt state. In the Rule 110 universal computer,
> > > "halt" is indicated by a certain breakdown in the usual behaviour
> > > of the patterns.
> >
> > Turing machines in the real world don't /actully/ come to a halt - in
> > the sense of the physics of the universe they are ceasing to function.
> >
> > They merely enter a different state, where they are no longer performing
> > their usual task.
> >
> > A Turing machine in a CA can do exactly the same thing.
>
> But I was not addressing the "Turing machine in a CA". I was addressing the
> same thing as the OP, xanthian and Andr?, which is a TM whose state table is
> based on directly simulating a Rule 110 CA, and whose tape contains initial
> data representing the pattern of the Rule 110 CA's universe, which in this
> case *happens* to contain a pattern which is performing a computation
> according to Matthew Cook's design (a "Turing machine in a CA").
What you /said/ you were talking about was "a Rule 110-based TM".
> The problem is that the state tables of the FSAs at the hearts of these very
> small TMs do not contain a halt state. They never halt. A TM which never
> halts is not very useful. A TM which never halts certainly cannot qualify
> as a UTM.
Surely such TMs with tiny numbers of states could signify a halt state -
by placing an X at some specified point on the tape during its evolution.
Would that not be sufficient to make it useful - and universal?
> > > (2) The initial tape must be infinite, because the initial Rule 110
> > > pattern is infinite, ie has an infinite nonblank portion.
> >
> > Similarly in the real universe. A Turing machine can't write on empty
> > space. It needs an infinite writable resource to operate on.
>
> A TM is defined, AFAIK, to have *access* to as long a tape as possible. Any
> new tape provided must be blank, ie every cell of the tape must contain a
> symbol previously agreed to be the "blank" symbol. (This is an important
> theoretical restriction, since it limits the input of a TM to a finite
> amount of information.)
It isn't a theoretical restriction - since limiting the input of a TM
to a finite amount of information is not normally done in that way.
For example, consider:
http://plato.stanford.edu/entries/turing-machine/
In its "formal definition" it specifies that the state of the TM must
correspond to a natural number. That means that the quantity
of information on the tape at any time must be finite - but it
*doesn't* constrain the tape to consist of the all-zero state.
It doesn't even specify that one of the tape symbols must be defined
as being "blank" - it just says the set of tape symbols must be finite.
So - according to that definition - a machine operating on an infinite
tape of alternating 0 and 1 symbols whould still qualify as a TM.
> We can "simulate" the static state of a TMs tape mathematically (which is a
> rather odd way to put it), by describing it as a function f:Z->S, where S is
> the symbol set of the TM, and where {i : f{i} ~= "blank"} is finite.
>
> A tape containing a Cook program in a Rule 110 CA has an *infinite* number
> of nonblank cells, and therefore is not a TM tape.
Turing tapes need not be constrained in that way.
There is no need to identify one of the tape states as being special
in some way when defining what a Turing machine is.
Kent Paul Dolan
Tim, for the sake of whatever remnant belief people
have in your potential sanity or your ever hoping to
recover it, try really, really hard this time to
come to the realization that:
> Turing machines in the real world
is an oxymoron, right at the beginning of your drift
away from rationality, and don't go there.
Watching you go off for dozens of postings of
increasingly bizarre (ir)rationalizations to defend
indefensible positions you should never have
undertaken in the first place, is a world class
example of something being Not A Fun Experience.
It was very much like watching (PhD) Julian Waldby
being overtaken by his manic phase until what he was
posting at the rate of dozens of articles per hour
wasn't even made of words any more.
It is just heartbreaking to watch a world-class
researcher decend into mindless gibbering as you did
last go-around on these issues.
Please take the trouble to spare us a reprise.
Thank you.
xanthian.
Markus Redeker
>The problem is that the state tables of the FSAs at the hearts of these
>very small TMs do not contain a halt state. They never halt. A TM which
>never halts is not very useful. A TM which never halts certainly cannot
>qualify as a UTM.
This makes the creation of a universal Turing machine via cellular automata
a much more demanding task. The UTM must
a) check for the "end of calculation" situation, and
b) provide for for a more copies of the background pattern, when needed.
Both can be done, but it increases the number of states immensely.
I don't think that anyone has tried to solve the problem with these
restrictions. Viewed this way, the number of states of a Turing machine that
only simulates the cellular automaton is almost useless.
Kent Paul Dolan
[sigh, I was too late, he's off and running again]
> Paul Chapman <pa...@igblan.free-online.co.uk> wrote or quoted:
>>>> A Rule 110-based TM is not a true TM, however,
>>>> for two reasons.
>>>> (1) The TM lacks a halt state. In the Rule 110
>>>> universal computer, "halt" is indicated by a
>>>> certain breakdown in the usual behaviour of the
>>>> patterns.
> http://plato.stanford.edu/entries/turing-machine/
> In its "formal definition" it specifies that the
> state of the TM must correspond to a natural
> number. That means that the quantity of
> information on the tape at any time must be finite
Give me strength.
No, that's NOT what it means. You have muddled what
they were talking about, the internal "state" of the
read-write head, by which it decides what to do in
response to the symbol it currently sees, with
another usage of state to describe the _entire_
Turing machine, that first "state" _plus_ the
current contents of the entire tape. Any sensible
look at their usage of "state" shows that they are
using it in the first sense, not the second, so you
are off marching into the weeds already.
> - but it *doesn't* constrain the tape to consist
> of the all-zero state.
Since "it" has nothing to do with the contents as a
whole of the tape, that's surely true by default.
> It doesn't even specify that one of the tape
> symbols must be defined as being "blank" - it just
> says the set of tape symbols must be finite.
No, "it" said something much stronger. Did you even
_read_ what you cited?
"Each cell is able to contain one symbol, either
‘0’ or ‘1’."
No "blank", no "halt here symbol".
As a result, the tape _must_ be preinitialized with
precisely one of "0" or "1" in _every_ cell, all
countably infinitely many of them.
> So - according to that definition - a machine
> operating on an infinite tape of alternating 0 and
> 1 symbols would still qualify as a TM.
The Rule 110 universal tag machine is implemented
with an infinite number of heads, which see three
cells, write one cell, all in parallel, and don't
move. This requires, for its operation, that it be
seeded with an infinitely wide repeated pattern,
spaceships IIUC, which virtually "move" instead,
to converge from left and right, collide, and thus
calculate, in some central, more chaotic portion
of the 1D CA.
A UTM is implemented with one head, which sees one
cell, writes or doesn't write one that cell, and
moves left, moves right, or stays put; it has no
requirement for an infinitely pre-seeded tape
creating a moving pattern in order for it to
operate.
The translation method between "them" need not leave
the UTM tape in the least bit resembling the Rule 110
starting row, in particular there is no requirement
that it contain infinite non-zeros to start.
Also, by your cited link, _every_ TM _always_ has a
halt state: any time it has no way to proceed or to
carry out the current state/symbol pair's command,
that constitutes a halt state, by the definition
explicitly given in the material you cited.
Since the TM tape is singly infinite, an attempt to
move off the finite end is therefore such a halt
state, and thus there _is_ a halt state.
xanthian.
Kent Paul Dolan
> b) provide for for a more copies of the background
> pattern, when needed.
No, you misunderstand.
A formal cellular automaton, like a formal Turing
machine, is an abstraction.
In the case of the TM, that means it has by
definition, a one dimentional tape of cells each
holding a single "bit", infinite in one direction.
[More complex alphabets are also allowed in
different TM definitions, but are provably
unnecessary; binary suffices, just as for
real world computers.]
In the particular case of the "Rule 110" cellular
automation, that means instead that it has by
definition a row of cells, infinite in _both_
directions, each cell also holding precisely one
bit.
For ease of reference (_only_), we usually number
the cells with the positive and negative integers in
the usual manner, just so we can have a "cell 0" to
make it meaningful to call some part the "center" of
the row, but the calculation in a formal sense is
unaware of these indices and treats "the center" no
differently than it treats any other part of the
row.
Conventionally, the TM tape is initialized to all
zeros except for some finite number of ones located
"near" the finite end of the tape, which constitute
the data on which the TM is to perform its
calculations until a halt state is achieved, if
ever.
In the case of the Rule 110 CA, the row of cells is
initialized, except for some central portion, with
two sets of patterns which converge (I don't know if
one moves or both) toward some finite original
central area where, again, the data which is to be
the subject of the CA's "calculation" is
initialized. In particular, since those two patterns
extend their repetitions endlessly to the left and
right, there is no need for a "glider gun" to
provide a continuous supply of new patterns, as you
suggest. An infinite supply already exists from the
first step of the calculation.
Moreover, there isn't _room_ for a "glider gun",
since there is no way to limit the amount of the
middle of the row that might become involved in the
calculation. And indeed, in the limit, the
calculation, in the equivalent of a TM falling into
an infinite loop walking away from the finite end of
the tape, might extend the "other than preset
pattern" central area "to" one or both infinite ends
of the CA row.
Never having read the Rule 110 a UTM writeup, I
have't a clue how the halt state is defined, but it
is bound to be messy, since with the row infinite
both ways and another step of the calculation always
possible, there is no "left end walk-off" available
as an easy choice to be the halt state.
This implies that some external-to-the-CA recognizer
for "halt" must exist. That offends my sense of order.
HTH
xanthian.
André Betz
completely suffice that there is a special state where the TM remains.
Tim Tyler
> Since the TM tape is singly infinite, an attempt to
> move off the finite end is therefore such a halt
> state, and thus there _is_ a halt state.
Defintions often specify an infinite extension in both directions - e.g.:
``The tape is assumed to be arbitrarily extendible to the left and to the
right, i.e., the Turing machine is always supplied with as much tape as
it needs for its computation.''
- http://en.wikipedia.org/wiki/Turing_machine
I don't think whether the tape in infinite or half-infinite is of
much significance.
For one thing:
``In our original formulation we specified that the tape had an end, at
the left say, and stretched infinitely far to the right. Relaxing this
stipulation to allow the tape to stretch infinitely far to right and
left results in a new formulation of Turing machines equivalent to the
original. That is for any Turing machine using a two way tape there is a
Turing machine with a one-way infinite tape with the same input-output
behavior, and vice versa.''
- http://plato.stanford.edu/entries/turing-machine/
Tim Tyler
> "Tim Tyler" <t...@tt1lock.org> wrote:
> > It doesn't even specify that one of the tape
> > symbols must be defined as being "blank" - it just
> > says the set of tape symbols must be finite.
>
> No, "it" said something much stronger. Did you even
> _read_ what you cited?
>
> "Each cell is able to contain one symbol, either
> ?0? or ?1?."
>
> No "blank", no "halt here symbol".
>
> As a result, the tape _must_ be preinitialized with
> precisely one of "0" or "1" in _every_ cell, all
> countably infinitely many of them.
It says that in the preamble at the top.
In the formal definition, it explicitly says a finite set
is allowed - and concludes with:
``This definition is very simlar to that given in the entry on
computability and complexity, with the significant difference that the
transition function may write a new symbol as well as move during any
transition. This change does not alter the set of Turing-computable
functions, and simplifies the formal definition by removing the second
condition on the transition function in our definition. Both formal
definitions permit the alphabet of symbols on the tape to be any finite
set, while the original definition insisted on S={0,1} this change also
does not impact the definition of the set of Turing-computable
functions.''
- http://plato.stanford.edu/entries/turing-machine/
Tim Tyler
> Tim, for the sake of whatever remnant belief people
> have in your potential sanity or your ever hoping to
> recover it, try really, really hard this time to
> come to the realization that:
>
> > Turing machines in the real world
>
> is an oxymoron, right at the beginning of your drift
> away from rationality, and don't go there.
Whether Turing machines can actually be constructed in
the real world is an issue of cosmology and physics
which is probably beyond the scope of this discussion.
For all we know, the real world could *be* a TM ;-)
Tim Tyler
> > Paul Chapman <pa...@igblan.free-online.co.uk> wrote or quoted:
> > http://plato.stanford.edu/entries/turing-machine/
>
> > In its "formal definition" it specifies that the
> > state of the TM must correspond to a natural
> > number. That means that the quantity of
> > information on the tape at any time must be finite
>
> Give me strength.
>
> No, that's NOT what it means. You have muddled what
> they were talking about, the internal "state" of the
> read-write head, by which it decides what to do in
> response to the symbol it currently sees, with
> another usage of state to describe the _entire_
> Turing machine, that first "state" _plus_ the
> current contents of the entire tape. Any sensible
> look at their usage of "state" shows that they are
> using it in the first sense, not the second, so you
> are off marching into the weeds already.
I read it wrong, sorry. It doesn't place any
constraints on the initial contents of the tape.
Ralph Hartley
> "André Betz" <ma...@andrebetz.de> wrote:
>
>>are there possible candidates and
>>research advances for smaller UTM's
>>than Rule110 ?
Lets go back to the original question, and ignore the totally pointless
discussion of whether rule 110 "really is" a UTM, which depends on fine
parsing of the definition of a TM. In the sense in which the many TM
definitions, and the myriad other models of computation, are equivalent,
Rule 110 is equivalent to them all. I *will* not discuss this further. Yawn.
> I would be mildly astonished if the answer
> to your query were in the affirmative
I would be mildly astonished if the answer were negative, subject to the
following caveat (which makes the question moot):
> how you measure "smaller" is going to be an issue
Exactly.
Rule 110 is smaller than the description of CAs in general, so it all
depends on what, and how, you count.
Are 5 apples "bigger" than 3 oranges? Don't you have to count the whole
tree they came from?
Be that as it may, I hope everyone agrees that Rule 110 is very small, when
viewed within its context (CAs).
It is quite surprising that complete models of computation can be that
small, but it is hardly new. Rule 110 is simple, but is not unique in that
respect.
Is there a general rule that in most contexts that *permit* universal
computation there will be a very small example? Answering that question
involves too many definitions to really be meaningful (so *please* don't
bother), but I hope you know what I mean.
Universal computation and/or undecidable problems are just not that rare!
In an effort to at least compare apples to other fruit, here are a couple
of more specific questions:
Is there a *proof* that is 110 the simplest universal *CA*? Are there
others with the same neighborhood and number of states? (don't count
trivial reflections etc.)
The only non-trivial neighborhoods smaller than 3 are two cell
neighborhoods, in which a cell interacts with its left and right neighbors
on alternate time steps (either all together or with alternating cells
looking in opposite directions).
i.e. either:
(A)
o o o o o o o
|/|/|/|/|/|/|
o o o o o o o
|\|\|\|\|\|\|
o o o o o o o
|/|/|/|/|/|/|
o o o o o o o
or
(B) (Margolis)
o o o o o o o
|X| |X| |X| |
o o o o o o o
| |X| |X| |X|
o o o o o o o
|X| |X| |X| |
o o o o o o o
(view "X" as two lines)
What is the smallest number of states for which there is a universal rule
on those neighborhoods? How does that change if we make further
restrictions (form of the rule, a quiescent state must exist etc.)?
What is the simplest *quantum* CA rule? How does it depend on the
definition of a quantum CA? (there is more than one) Reversible classical
CAs are a subset of quantum CAs, but is there a quantum rule with a smaller
neighborhood? (For technical reasons, QCAs are easier to define on
neighborhood (B).) What if we require it to be complete for quantum
computation as well?
With the *possible* exception of my very last question (which I am too
interested in to let drop, but too lazy, so far, to answer :-)), the
practical consequences of all this are precisely nil. The simple universal
systems are not remotely practical. They would only really matter if there
were a physical implementation so efficient that it overcame the overhead
involved in compiling programing languages for them.
It's an interesting game anyway.
Ralph Hartley
r.e.s.
> Lets go back to the original question, and ignore the totally pointless
> discussion of whether rule 110 "really is" a UTM, which depends on fine
> parsing of the definition of a TM. In the sense in which the many TM
> definitions, and the myriad other models of computation, are equivalent,
> Rule 110 is equivalent to them all.
It's neither pointless, nor "fine parsing" of the definition to
question what you claim in that last sentence.
If a so-called "computation" never halts, and *also* never makes
it possible to identify the *result* of a desired computation
(i.e. what may be called the answer to a computational question),
then the so-called "computation" is not a computation at all --
by even the crudest of measures. It isn't enough to know that
the answer to a question is some item somewhere in an infinite
list -- it's necessary to identify which item it is.
> I *will* not discuss this further. Yawn.
-snip-
There's a old story about three monkeys. I think they yawned
quite a bit, too.
> The simple universal systems are not remotely practical. They
> would only really matter if there were a physical implementation
> so efficient that it overcame the overhead involved in compiling
> programing languages for them.
Lacking a means to identify the result of a computation when
the CA eventually produces it, as it continues without halting,
would seem to be at least as much reason to call it impractical.
--r.e.s.
Tim Tyler
> Also, by your cited link, _every_ TM _always_ has a
> halt state: any time it has no way to proceed or to
> carry out the current state/symbol pair's command,
> that constitutes a halt state, by the definition
> explicitly given in the material you cited.
Indeed.
With hindsight - it's not how I would have done things:
A TM /already/ has an output stream for communicating with
the rest of the world with. It has no need at all for a
separate independent communication channel down which it
can only ever communicate one bit.
The provision of a second such communications channel pointlessly
complicates the definition of a Turing machine - without any
compensating improvement in its behaviour.
If you remove a Turing machine's halt state you can still
prove all the same theorems using it.
Since one of the main points of a Turing machine is that it
is an abstract model of serial computation, such unnecessary
and superfluous features seem rather undesirable.
Russell Easterly
"Tim Tyler" <t...@tt1lock.org> wrote in message news:I9r9I...@bath.ac.uk...
> Kent Paul Dolan <xant...@well.com> wrote or quoted:
>
> > Also, by your cited link, _every_ TM _always_ has a
> > halt state: any time it has no way to proceed or to
> > carry out the current state/symbol pair's command,
> > that constitutes a halt state, by the definition
> > explicitly given in the material you cited.
A TM does not have to have a halt state.
It may be that the TM's described in the paper above
always have halt states because the paper assumes
the input tape length is fixed or that some state is not defined
for every input.
Some people define HALT as a state.
In other words, the TM halts when it enters
that state regardless of what is on the input tape.
I prefer to define halt as a command that can
be executed for a specific input.
If a TM's every state has a non-halting action defined
for every input, then that TM has no halt states and
it will never halt.
I normally insist that HALT be a command
(as opposed to the lack of a command.)
This makes enumerating TM's a lot easier.
Every state has a defined action for every input.
> If you remove a Turing machine's halt state you can still
> prove all the same theorems using it.
>
It would be hard to prove the Halting problem only
using TM's that never halt.
I would say almost nothing is provable if you remove
all the halt states from a TM.
For example, theorems are suppose to be finite in length.
How would you prove finiteness with a TM that never halts?
Russell
- 2 many 2 count
Kent Paul Dolan
> A TM /already/ has an output stream for
> communicating with the rest of the world with.
Well, no, it doesn't. The tape is like Hawking's
concept of time, it doesn't "flow", and it isn't "a
stream"; it just sits there. An "output stream"
would be an out of band record of the read head
symbol seen, symbol written, motion taken, state
entered (implicit, but still...) transitions, which
is hugely more of a mess than "halted" to take out
the side of the instrument.
> It has no need at all for a separate independent
> communication channel down which it can only ever
> communicate one bit.
That, again, profoundly misunderstands that a TM is
not a real world device. TM tapes come in three
forms useful to the observer: tapes containing data
in work, including freshly initialized with a
problem, tapes containing worked results, and tapes
in some Heisenberg state in between because the
computation failed to halt.
Since the TM is an abstraction, there is no "wait"
involved, start the computation, and it is done in
imperceptible time, or start the computation, and it
is never done. Being able to distinguish those two
situations is crucial.
> The provision of a second such communications
> channel pointlessly complicates the definition of
> a Turing machine - without any compensating
> improvement in its behaviour.
I hear, once again, you having been caught in an
error ("TMs can exist that have no halt state") and
now trying to patch reality retroactively to make
your error never have occurred, first by trying to
get rid of the non-infinite end of the tape where
the collision that spells "halt" occurred, by
diverting attention to an alternative definition of
a TM than the very one you gave us as your
"authoritative reference", now second by trying to
wave your hands and make "halt" not a part of the TM
definition.
Could we not go through this exercise in idiocy yet
again? You were wrong, and wrong in public, and like
Humpty Dumpty, the damage is irreversable even in
the fairy tale universe where you seemingly want to
choose to dwell.
Suck it up, Tim, and learn to cope with your own
fallibility as a normal part of human experience
instead of letting evidence of it make you behave
insanely in denial of your errors. No one at all
respects someone who won't admit his errors _and_
live with that admission.
Since almost every result in computer science about
TM use involves the result when and if the TM halts,
I'm afraid you have, yet again, performed a "Tim
Tyler into Bozoland" excursion. Is it really this
hard for someone with a CS(?) PhD to grasp Turing
Machines as the abstraction they are?
> If you remove a Turing machine's halt state you
> can still prove all the same theorems using it.
That would be a bit astonishing. How, for example,
would you prove the non-existence of a halting
problem solver, probably the single most important
contribution of the TM abstraction to the field of
practical computing, without the concept of a halt
state?
> Since one of the main points of a Turing machine
> is that it is an abstract model of serial
> computation, such unnecessary and superfluous
> features seem rather undesirable.
I cannot fathom how the "out of band" detection of a
Rule 110 Universal Tag Machine's "halting" is
superior to the "the computation is not incomplete"
out of band detection of a TM halting.
The only "undesirable" aspect of the halt state is
that you were caught in an error denying its
existence. Just how much of our, and your, time and
intellectual capital do you intend to waste this
time around purusing the correction of this suddenly
discovered "undesirable feature" of the Turing
machine definition now standard for 70 or so years?
You are putting yourself on a precise intellectual
level with Peter Olcott and James Harris with this
behavior, which is a disgusting thing for someone
of your talent and accomplishments to be doing and
to be seen doing.
Could you cruise back toward the intellectual
landscape where the rest of us somehow manage to
dwell without insurmountable difficulties sometime
soon, so meaningful discussion returns to being a
possibility?
I suggest you practice standing in front of a mirror,
looking yourself straight in the eyes, and saying "I
am wrong, and everyone knows I am wrong" until the
urge to cut your throat or kill someone goes away
forever, deadened from being too often provoked.
As noted before, watching you indulging in these
fiascos is the precise opposite of "fun".
Kent Paul Dolan
>> xanthian wrote:
>>> Also, by your cited link, _every_ TM _always_ has a
>>> halt state: any time it has no way to proceed or to
>>> carry out the current state/symbol pair's command,
>>> that constitutes a halt state, by the definition
>>> explicitly given in the material you cited.
> A TM does not have to have a halt state.
Please point out the exact words in the
paragraph above your bogus claim which you
were incapable of tranlating into Russellese,
and I'll try to find a trained ape to teach
you enough more of English that you can cope.
Tim Tyler
> "Tim Tyler" <t...@tt1lock.org> wrote in message news:I9r9I...@bath.ac.uk...
> > Kent Paul Dolan <xant...@well.com> wrote or quoted:
> > > Also, by your cited link, _every_ TM _always_ has a
> > > halt state: any time it has no way to proceed or to
> > > carry out the current state/symbol pair's command,
> > > that constitutes a halt state, by the definition
> > > explicitly given in the material you cited.
>
> A TM does not have to have a halt state.
Well, it looks like they do, by definition.
> It may be that the TM's described in the paper above
> always have halt states because the paper assumes
> the input tape length is fixed or that some state
> is not defined for every input.
Check with some other definitions. They agree on this point.
> > If you remove a Turing machine's halt state you can still
> > prove all the same theorems using it.
>
> It would be hard to prove the Halting problem only
> using TM's that never halt.
Not so. The machine is /still/ capable of signalling
whatever it likes - by writing on the tape. You would
simply define "finishing" to be leaving some defined
mark at a defined point on the tape.
> I would say almost nothing is provable if you remove
> all the halt states from a TM.
Clearly, that would be totally incorrect.
Tim Tyler
> "Tim Tyler" <t...@tt1lock.org> wrote:
[Systems with no "halt" state]
When using quote marks, it is conventional to
cite material which was /actually/ said.
In this case, I simply never uttered the quoted material.
> > If you remove a Turing machine's halt state you
> > can still prove all the same theorems using it.
>
> That would be a bit astonishing. How, for example,
> would you prove the non-existence of a halting
> problem solver, probably the single most important
> contribution of the TM abstraction to the field of
> practical computing, without the concept of a halt
> state?
You would define "finishing" to be leaving a specified
mark at a specified point on the tape. That's
how conventional Turing machines leave the rest
of their output - communicating that the machine
has finished its task need not be any different.
> > Since one of the main points of a Turing machine
> > is that it is an abstract model of serial
> > computation, such unnecessary and superfluous
> > features seem rather undesirable.
>
> I cannot fathom how the "out of band" detection of a
> Rule 110 Universal Tag Machine's "halting" is
> superior to the "the computation is not incomplete"
> out of band detection of a TM halting.
As I mentioned, it complicates the definition of
a TM with something completely unnecessary - a
dedicated halt state built into the machine itself.
Remove such states and you can still prove all the
same theorems. The use of such a state is redundant.
Markus Redeker
>"Markus Redeker" <c...@ibp.de> wrote:
>> b) provide for for a more copies of the background pattern, when needed.
>No, you misunderstand.
No, I didn't write clearly enough :)
First of all, with "Turing machine" I mean a TM with a single tape, infinite
in both directions. The tape is initialized with zeroes, except for a finite
number of tape cells.
On such a tape, one can simulate a linear cellular automaton, like rule 110,
with a relatively simple Turing machine, having few states and tape symbols.
(But I haven't seen its definition. Where ist it?)
Rule 110 is computationally universal, so one can think that one can use the
Rule 110 TM to get a universal TM by encoding the problem as a Rule 110
pattern.
This is possible, but I think it increases the number of states of the TM
considerabely. Because the tape is filled with zeroes but Matthew Cook's
construction requires that to both directions the tape is filled with
repeated patterns (one of them representing the problem), the TM has to
simulate a finite portion of the cellular space, with "end" markers on both
sides, adding more copies of the repeated patterns before it moves beyond
the markers.
This is exactly the problem I wanted to mention in the one sentence you
quoted from me...
Tim Tyler
> On such a tape, one can simulate a linear cellular automaton, like rule 110,
> with a relatively simple Turing machine, having few states and tape symbols.
> (But I haven't seen its definition. Where ist it?)
There's a definition of a machine with two states and five "colours" on
page 707 of A New Kind of Science.
Steven Wolfram calls it "The simplest Turing machine currently known to be
universal".
The machine operates by simulating rule 110.
Kent Paul Dolan
[whine about paraphrase being in quote marks]
Gut it out Tim, this is your game, played to
cater to your obsessions, not mine.
> You would define "finishing" to be leaving a
> specified mark at a specified point on the tape.
> That's how conventional Turing machines leave the
> rest of their output - communicating that the
> machine has finished its task need not be any
> different.
Do you bother to think at all before you post such
idiocy, or is this obsessive-compulsive behavior
cause by your inability to accept your being in
error?
When did the definition of a TM get modified to
include the enhancement of an oracle that is aware
of the entire current state of the tape in parallel,
checks the tape at _every_ step of the calculation
(since your scheme doesn't at all prevent the TM,
having finished its designed purpose, from promptly
overwriting the "halt marker", though that's not
insurmountable in and of itself), and then as an
oracle signals the TM to stop computing, and the
user that the computation is done?
What makes you think the tape has _room_ for a halt
marker? If the calculation never halts, then it can
fill the tape with rubbish to infinity, and you
cannot claim "by design", because to do, for
example, the proof of the nonexistence of a halting
problem solver, the TM needs to be able to accept
_any_ problem, not just ones tailored to leave room
for a halt marker.
You were just complaining about a one-bit output
"halted" from the TM, so to replace you insert
something that needs an oracle _and_ a one bit
"halted" output? Once again, you have failed to
satisfy the need to deliver the information to the
user.
Just as with your previous attempts to fill all of
space and time with wiring for a physically realized
CA, to compensate for a similar failure to consider
the need to deliver the result to the user, you are
simply piling new idiocy on new idiocy to avoid
facing yourself and admitting you are wrong.
> As I mentioned, it complicates the definition of
> a TM with something completely unnecessary - a
> dedicated halt state built into the machine itself.
Which you have only replaced with an oracle, since
the user, not being omnicient, _still_ needs a way
to know the computation is complete, and cannot act
as a watchdog on the TM, monitoring the results of
every step.
> Remove such states and you can still prove all the
> same theorems. The use of such a state is
> redundant.
Well, no, you are just being an "Ossa on
Pelion"-piling moron again, adding one impossiblity
to replace each demolished one, which doesn't prove
anything except your apparently endless capacity for
self delusion.
Could we stop playing this game now, or do you need
to satisfy some inner urge for writing a particular
quantity of imbecilic followups before you weary of
being compulsively stupid?
xanthian.
Don't bother to answer the challenges to your
arguments until you can answer the challenge to why
you are wasting time writing them. Any other
response will be happily ignored. If you think you
have thereby "won", merely by getting the last word
through repeatedly applied insanity, you are more
mentally ill than I am.
Kent Paul Dolan
> omnicient
Sigh.
s/omnicient/omniscient/
Being able to spell doesn't help if your typing
is slowly but surely decaying with age, and I
was never that good at spelling in the first
place anyway.
xanthian.
Tim Tyler
> Don't bother to answer the challenges to your
> arguments until you can answer the challenge to why
> you are wasting time writing them.
I think I'm mostly replying for the same main reason why I
participate in usenet in the first place - in the hope of
learning things.
While debate with you in this forum often seems to produce
more heat than light, you /did/ successfully manage to point
out a problem in my argument earlier in this thread - a fact
for which I'm grateful.
Tim Tyler
> Since one of the main points of a Turing machine is that it
> is an abstract model of serial computation, such unnecessary
> and superfluous features seem rather undesirable.
Another problem I see with Turing machines as an abstract model
of serial computation is that they are *defined* as only having
"back" and "forward" states.
What's with that?
It causes most two-dimensional serial digital machines to fail to
qualify as a Turing machines :-(
I can't help but think that - if Turing was alive today - he'd
define things differently - so that a Turing machine was a more
general model of a serial machine - rather than being a model
of a tiny subset of them.
Torkel Franzen
> I can't help but think that - if Turing was alive today - he'd
> define things differently - so that a Turing machine was a more
> general model of a serial machine - rather than being a model
> of a tiny subset of them.
No he wouldn't.
Rick Decker
Tim Tyler wrote:
> I, Tim Tyler <t...@tt1lock.org> wrote or quoted:
>
>
>>Since one of the main points of a Turing machine is that it
>>is an abstract model of serial computation, such unnecessary
>>and superfluous features seem rather undesirable.
>
>
> Another problem I see with Turing machines as an abstract model
> of serial computation is that they are *defined* as only having
> "back" and "forward" states.
>
> What's with that?
>
> It causes most two-dimensional serial digital machines to fail to
> qualify as a Turing machines :-(
No it doesn't. The inclusion of a two-dimensional "tape" along
with forward/back/up/down moves of the head gives you a machine
that is equivalent to a vanilla TM. Many intro theory texts
contain proofs of this.
Regards,
Rick
tc...@lsa.umich.edu
>Another problem I see with Turing machines as an abstract model
>of serial computation is that they are *defined* as only having
>"back" and "forward" states.
Turing's purpose was to establish the limits of computation, not to
construct a faithful model of specific computer architectures.
For the purposes of answering questions about whether there exists an
algorithm of *any* sort for a particular problem, details of the kind
you are worried about don't really matter; the relevant question is
whether a computation on some other kind of computer with a different
architecture can be *simulated* by a Turing machine. As long as the
Turing machine can do this, it succeeds in its intended purpose.
Certainly one can ask more specific questions about computers, whose
answers *do* depend on a specific choice of architecture, and in those
contexts, a Turing machine might not be the most appropriate model.
But then you're changing the question.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
Markus Redeker
>There's a definition of a machine with two states and five "colours" on
>page 707 of A New Kind of Science.
>Steven Wolfram calls it "The simplest Turing machine currently known to be
>universal".
>The machine operates by simulating rule 110.
It is as I suspected: the machine can simulate rule 110 only for patterns
that consist of a finite region of ones and zeroes, surrounded by zeroes.
Matthew Cook's universal tag systems are not among them. Therefore I
conclude that the Turing machine maybe universal, but it is definitely not
proven. (And I didn't even talk about the missing "halt" state!)
At least the Turing machine will inherit the unpredictability from the
cellular automaton.
Tim Tyler
AFAICS, machines with Up/Down/Left/Right operations fail to qualify as
Turing machines - according to most popular definitions.
In particular, they fail according to definitions on the previously-cited
pages:
http://plato.stanford.edu/entries/turing-machine/
...and...
http://en.wikipedia.org/wiki/Turing_machine
Of course a 2D machine can do all the same computations a one
dimensional machine can do - but being "Turing equivalent" is
not the same as being a "Turing machine".
Tim Tyler
> >Another problem I see with Turing machines as an abstract model
> >of serial computation is that they are *defined* as only having
> >"back" and "forward" states.
>
> Turing's purpose was to establish the limits of computation, not to
> construct a faithful model of specific computer architectures.
>
> For the purposes of answering questions about whether there exists an
> algorithm of *any* sort for a particular problem, details of the kind
> you are worried about don't really matter; the relevant question is
> whether a computation on some other kind of computer with a different
> architecture can be *simulated* by a Turing machine. As long as the
> Turing machine can do this, it succeeds in its intended purpose.
If that were the case, wouldn't a Turing machine be a specific
abstract machine?
Definitions of Turing machines these days explicitly permit
arbirtary sets of symbols in the head and arbitrary sets of
symbols on the tape. It seems that they are attempting to
deal with a general class of machines - not just one machine
to which other serial devices are compared.
If you are going to be specific, it would make sense to be
*completely* specific.
It's the mixture of being specific when it comes to the movement actions,
but general when it comes to the symbols that seems to be an incongruity.
Rick Decker
Tim Tyler wrote:
> Rick Decker <rde...@hamilton.edu> wrote or quoted:
>
>>Tim Tyler wrote:
>>
>>>I, Tim Tyler <t...@tt1lock.org> wrote or quoted:
>
>
>>>>Since one of the main points of a Turing machine is that it
>>>>is an abstract model of serial computation, such unnecessary
>>>>and superfluous features seem rather undesirable.
>>>
>>>Another problem I see with Turing machines as an abstract model
>>>of serial computation is that they are *defined* as only having
>>>"back" and "forward" states.
>>>
>>>What's with that?
>>>
>>>It causes most two-dimensional serial digital machines to fail to
>>>qualify as a Turing machines :-(
>>
>>No it doesn't. The inclusion of a two-dimensional "tape" along
>>with forward/back/up/down moves of the head gives you a machine
>>that is equivalent to a vanilla TM. Many intro theory texts
>>contain proofs of this.
>
>
> AFAICS, machines with Up/Down/Left/Right operations fail to qualify as
> Turing machines - according to most popular definitions.
>
> In particular, they fail according to definitions on the previously-cited
> pages:
>
> http://plato.stanford.edu/entries/turing-machine/
>
Look at section 3: Varieties of Turing Machines. In the first paragraph
they say:
There are a number of variations to the formulation that turn out to
be equivalent to this one, and different authors present Turing
machines using any of these. Since they are all provably equivalent
to one another we can consider any of the formulations as being the
definition of Turing machine as we find convenient.
They then go on to describe a 2D TM, among others.
>
> http://en.wikipedia.org/wiki/Turing_machine
>
> Of course a 2D machine can do all the same computations a one
> dimensional machine can do - but being "Turing equivalent" is
> not the same as being a "Turing machine".
Oh for heaven's sake. If it quacks like a TM, it may as well
be regarded as a TM. However, if you wish to include only
one-semi-infinite-tape, one-head, whatever ... machines in
your classification of TMs, go right ahead.
I take it you would disallow multi-tape TMs, since they're
not mentioned in the definition on the Stanford page.
Regards,
Rick
Kenneth Doyle
> It causes most two-dimensional serial digital machines to fail to
> qualify as a Turing machines :-(
>
A Turing machine has infinite storage capacity. That seems to me to be a
more fundamental disqualifier for any physical machine. In any event, it
doesn't matter. The whole purpose of the exercise is not to build the
machine, but to study the implications of such a machine's (postulated)
existence. It's mathematics, not engineering.
Tim Tyler
That's right. If you allow parallel computation - or if
you allow anything that can produce the same output to
be called a TM - then the Turing machine loses one of its
more positive characteristics - that it is a model of
*serial* computation.
Rick Decker
I guess, then, that you'd *really* be opposed to considering
anything like a nondeterministic TM.
Tell you what--how about you come up with a model of serial
computation that fixes Turing's 1936 "mistake." What about
an abacus machine as defined on the Stanford site? Would
you consider that acceptable?
Regards,
Rick
tc...@lsa.umich.edu
>If that were the case, wouldn't a Turing machine be a specific
>abstract machine?
That is the point of the concept of a universal Turing machine (isn't
that how this thread started?).
>Definitions of Turing machines these days explicitly permit
>arbirtary sets of symbols in the head and arbitrary sets of
>symbols on the tape. It seems that they are attempting to
>deal with a general class of machines - not just one machine
>to which other serial devices are compared.
Typically, these variations are examined in order to show that the
definition is robust, i.e., that these variations don't really affect
the questions of interest.
Anyway, the point is, it is certainly true that if you're interested
in peculiarities of particular computer architectures, then the Turing
machine model isn't necessarily the best one. This is a well-understood
fact, which is why there are so many different models of computation out
there in the literature. But the existence of these other models doesn't
mean that the Turing machine model is deficient, for it perfectly well
serves the purpose for which it was intended.
Tim Tyler
> >If that were the case, wouldn't a Turing machine be a specific
> >abstract machine?
>
> That is the point of the concept of a universal Turing machine (isn't
> that how this thread started?).
Turing machines are not defined to be a /specific/ abstract machine.
Rather they are defined to be a /class/ of such machines.
> >Definitions of Turing machines these days explicitly permit
> >arbirtary sets of symbols in the head and arbitrary sets of
> >symbols on the tape. It seems that they are attempting to
> >deal with a general class of machines - not just one machine
> >to which other serial devices are compared.
>
> Typically, these variations are examined in order to show that the
> definition is robust, i.e., that these variations don't really affect
> the questions of interest.
They are present in the fabric of the definition itself.
If examining variations to show robustness, why are variations
in the number of head states and number of tape states included -
but variations in the number of movement directions are not?
Mitch Harris
> In comp.theory.cell-automata tc...@lsa.umich.edu wrote or quoted:
>>In article <I9t8t...@bath.ac.uk>, Tim Tyler <t...@tt1lock.org> wrote:
>
>>>Definitions of Turing machines these days explicitly permit
>>>arbirtary sets of symbols in the head and arbitrary sets of
>>>symbols on the tape. It seems that they are attempting to
>>>deal with a general class of machines - not just one machine
>>>to which other serial devices are compared.
>>
>>Typically, these variations are examined in order to show that the
>>definition is robust, i.e., that these variations don't really affect
>>the questions of interest.
>
> They are present in the fabric of the definition itself.
In the sense that one can derive them, yes. Definitions have all
sorts of implications. Some are easily derivable, others not.
> If examining variations to show robustness, why are variations
> in the number of head states and number of tape states included -
> but variations in the number of movement directions are not?
Taste.
--
Mitch Harris
(remove q to reply)
Ralph Hartley
> "Tim Tyler" <t...@tt1lock.org> wrote:
>
>>You would define "finishing" to be leaving a
>>specified mark at a specified point on the tape.
>>That's how conventional Turing machines leave the
>>rest of their output - communicating that the
>>machine has finished its task need not be any
>>different.
>
> Do you bother to think at all before you post such
> idiocy
Do you bother to read what you quote before you call the poster names?
You might argue that it is a mater of a stopped clock being right twice a
day, but Tim's quote above is correct.
Placing a *specified* mark at a *specified* point is a perfectly reasonable
way for a machine to signify that it is finished.
A machine that signifies "halt" in that way is computationally equivalent
to the more common definition.
> When did the definition of a TM get modified to
> include the enhancement of an oracle that is aware
> of the entire current state of the tape in parallel,
> checks the tape at _every_ step of the calculation
> (since your scheme doesn't at all prevent the TM,
> having finished its designed purpose, from promptly
> overwriting the "halt marker", though that's not
> insurmountable in and of itself), and then as an
> oracle signals the TM to stop computing, and the
> user that the computation is done?
Nothing of the kind is required. One need only watch that one bit, if it
ever changes, that is equivalent to halting. It doesn't matter if it gets
overwritten since the computation is by definition finished the first time
it changes (though it is always possible to construct the TM so that it
never does).
After all, the most common physical system used to *implement* computation
- (electronic) digital logic - doesn't ever stop ether.
One could argue that it cannot *perfectly* simulate a TM, because it has a
nonzero error rate, because memory is not infinite, or because it can never
continue computing forever (for some reason I rarely see that one), but
*not* because it doesn't "halt". You can wire one bit to a bell or something.
Actually, that is an answer to the original question. Circuits made of nand
gates are computationally complete, and the nand gate:
0 1
- -
0 | 1 1
1 | 1 0
is arguably simpler than rule 110.
From a *computational* viewpoint it isn't even required that the "halt"
symbol be at a specific place, since a TM could move it. There *are* cases
where it makes a difference to *complexity*.
> What makes you think the tape has _room_ for a halt
> marker? If the calculation never halts, then it can
> fill the tape with rubbish to infinity, and you
> cannot claim "by design", because to do, for
> example, the proof of the nonexistence of a halting
> problem solver, the TM needs to be able to accept
> _any_ problem, not just ones tailored to leave room
> for a halt marker.
I have noticed in that past that your posts tend to be correct, but very
insulting. What went wrong this time?
A UTM need not allow the TM it is simulating to access every cell of its
own tape. It can reserve the leftmost cell, or all odd numbered cells etc.,
for its own use.
"Room" doesn't work exactly in the intuitive way on an infinite tape, since
infinity-1 = infinity/2 = infinity (I mean countable infinity).
I *know* you know all this!
> Just as with your previous attempts to fill all of
> space and time with wiring for a physically realized
> CA, to compensate for a similar failure to consider
> the need to deliver the result to the user
In that case he was talking about complexity, and did not include the
requirement that the mark be in a particular place. He was completely wrong
that time.
> If you think you
> have thereby "won", merely by getting the last word
> through repeatedly applied insanity, you are more
> mentally ill than I am.
Correct. I know you all have *much* more free time than I do, so I never
expect the last word. Nor do I expect to convince the poster himself, that
would be unrealistic.
The intended beneficiaries of a usenet posting should always be the lurkers.
Ralph Hartley
Kent Paul Dolan
> I have noticed in that past that your posts tend
> to be correct, but very insulting. What went wrong
> this time?
[My posts tend to grow insulting only into the teeth
of obdurate idiocy, such as Tim's in this and the
preceding discussion; I'm quite capable of collegial
responses, though finding people civilized enough to
merit them grows increasingly difficult with time.]
1) You failed to think through your criticisms.
2) I wasn't nearly insulting enough to derail
Tim's ongoing drift into life-destroying
behaviors. As he's much more intelligent than
I am, it will probably take someone at his own
level to help him break free of this illness.
Tim's claim was that a "TM" need not have "a halt
state", but all his solution, or your echoing of it,
has accomplished is to push that halt state from
"the states internal to the read-write head" to "the
state of the TM as a whole including its tape and
considered across every step of its computation",
and the objection to having a wire coming out the
side of the read write head with a toggle for
"halted" signaled on it is no different than an
objection to the wiring of one cell of the TM's tape
to the observer's eye [which you've now merely
incorporated into the computer as my earlier
mentioned "oracle"; of what possible use is a
"computer" which must be constantly monitored; the
main goal of computers is to free people's time to
do other stuff], or to a bell, to convey a toggle
for "halted".
A TM, _by definition_, has a halt state, and Tim's
disliking that part of the definition doesn't change
its validity at all, nor does his hand-waving claim
for the capabilities of a haltless TM being
unimpaired to do "TM-stuff" like disproving the
existence of a halting problem solver do anything to
make such claims true.
Just since you asked,
xanthian.
Tim Tyler
> Tim's claim was that a "TM" need not have "a halt
> state", but all his solution, or your echoing of it,
> has accomplished is to push that halt state from
> "the states internal to the read-write head" to "the
> state of the TM as a whole including its tape and
> considered across every step of its computation",
> and the objection to having a wire coming out the
> side of the read write head with a toggle for
> "halted" signaled on it is no different than an
> objection to the wiring of one cell of the TM's tape
> to the observer's eye [which you've now merely
> incorporated into the computer as my earlier
> mentioned "oracle"; of what possible use is a
> "computer" which must be constantly monitored; the
> main goal of computers is to free people's time to
> do other stuff], or to a bell, to convey a toggle
> for "halted".
If you want to criticise the idea of removing
the constraint that these abstract machines
must have a dedicated halt state wired into their
heads, one point you might like to focus on is
whether the resulting machine is still a serial
device.
Criticisms in that area would at least have the
virtue of having some validity.
André Betz
> more fundamental disqualifier for any physical machine. In any event, it
I don't think that it says that you must have infinite memory. I think
the definition of a TM ist that you hav enough memory for the operation.
If you need only 6kByte than you construct a TM with a Type that
contains only that amount of memory. If you want to calculate the
numbers of Pi you need infinite memory.
--
André Betz
Kontakt: http://www.andrebetz.de/sign.txt
Mcintosh Harold V.
news:I9u37...@bath.ac.uk
> If examining variations to show robustness, why are
> variations in the number of head states and number
> of tape states included - but variations in the number
> of movement directions are not?
But they are, although I would have to do some searching
to find a reference to establish the point. But there
really are Multidimensional Turing Machines, and they
are equivalent to the canonical machine.
By the way, this does not include "infinite dimensional,"
and using real numbers as a state set isn't canonical
either.
- hvm
Ralph Hartley
> By the way, this does not include "infinite dimensional,"
> and using real numbers as a state set isn't canonical
> either.
Well, an infinite dimensional tape doesn't in itself do any harm, since the
finite state control part of a TM can never actually use more than a finite
number of directions.
To make a non TM-equivalent "infinite dimensional TM" you would at least
have to add some sort of new primitive like "move head A in the direction
indicated by the number encoded on tape B."
Even then, it isn't clear that it isn't *still* TM-equivalent, unless you
allow more than a finite number of non-blank cells on the initial tape, or
something equally unreasonable.
There are many ways to add real numbers without changing the computational
class too. But you have to be careful. Of course there are non-computable
real numbers, and allowing one of those to be part of the specification of
a machine clearly *would* make a difference.
Ralph Hartley
Tim Tyler
> "Tim Tyler" <t...@tt1lock.org> wrote in message
> > If examining variations to show robustness, why are
> > variations in the number of head states and number
> > of tape states included - but variations in the number
> > of movement directions are not?
>
> But they are, although I would have to do some searching
> to find a reference to establish the point. But there
> really are Multidimensional Turing Machines, and they
> are equivalent to the canonical machine.
Do you consider every machine which is Turing-equivalent
to be a Turing machine?
If so, why does the term "Turing equivalent" exist?
Why don't all machines that can compute the same functions
as Turing machines get classified as *being* "Turing machines" -
rather than being merely "Turing equivalent".
tc...@lsa.umich.edu
>Do you consider every machine which is Turing-equivalent
>to be a Turing machine?
I can't speak for Harold Mcintosh, but the best answer is "it depends."
What question are you trying to ask?
Sometimes in mathematics, two things are regarded as being the same, and
other times they are not. It depends on context whether it is better to
ignore the differences or to emphasize them.
For the purposes of setting down a precise definition in order to get the
subject started, details matter. That is, you have to decide how many
tapes you will allow, what kind of symbols you will allow, and so forth.
Further along the path, when you're trying to figure out whether your
definition is robust and whether it seems to be powerful enough to simulate
everything that you want it to simulate, you may wish to regard everything
that is "Turing equivalent" to your original definition as the same. This
is especially important when you're going to investigate Turing degrees of
unsolvability, for example.
Still further along the path, when you want to investigate peculiarities of
certain computer architectures (as you seem to want to do with your repeated
mention of "serial machines"), you may wish to re-introduce distinctions
that were ignored previously, or invent new definitions.
The important thing is that you state your goals clearly, choose your
definitions appropriately for the task at hand, and warn the reader about
any deviations you make from standard terminology and why you're making
those deviations.
Mcintosh Harold V.
> Do you consider every machine which is Turing-equivalent
> to be a Turing machine?
What I personally consider may not be what someone else
would say; also consider that informal discussion may not
be what one would wrinte in a formal presentation.
On one level, there are variants on the "checking squares
on a roll of paper" theme wherein the tape can be erased
or not, whether multiple tapes can be used, dimensionality
of the writing surface varies, many or few states and
symbols can be used, and so on. Some results are probably
pure playing; others such as the exchange of states for
symbols are both interesting and useful. The essential
equivalence of quite a few of these variants has been
studied and documented; the results may have been foreseen,
nevertheless it is reassuring to have them.
On another level, the whole mechanism changes: think of
Gödel numbers, the Lambda Calculus, Markov Algorithms,
Post Systems, and even WireWorld and IBM 709's. Still,
they all compute the same things and give the same
results, which leads to Church's Thesis, that there is
only one kind of computation, or Turing's thesis, that
his little machine does it. On a practical level, they
all compute the same things because the core mechanism
of any of them can be programmed in the others, so it is
never necessary to compare the actual computations.
> If so, why does the term "Turing equivalent" exist?
I guess, it is because of this other level. Would you
say that factoring large primes is the same as scribbling
tally marks on a roll or paper? Or just that you can
(presumably) solve the same problems get the same results
either way?
> Why don't all machines that can compute the same functions
> as Turing machines get classified as *being* "Turing machines" -
> rather than being merely "Turing equivalent".
I doubt that Post would have liked that!
McIntosh Harold V.
news:41d8262c$0$14606$ed26...@ptn-nntp-reader01.plus.net
> A tape containing a Cook program in a Rule 110 CA has an
> *infinite* number of nonblank cells, and therefore is not
> a TM tape.
A similar question comes up when one observes that Rule 110
has an "ether" rather than a "vacuum" and wonders whether it
can be placed in Class IV, whether its "gliders" are really
gliders, and so on, including the observation that "if a
general purpose computer is needed to prepare the input,
then it is still not clear whether the machine which takes
over at that point is general purpose (i.e., universal) or
not."
Once solid details of Cook's scheme were available, all of
these doubts became secondary, although they still remain.
What is important is that fixed structures are placed at the
far west and far east and thereafter do not change until
they participate in the the computation. Setting up the
sandwich for a particular computation can still be pretty
complicated, but I don't think that it counts as an
objection any more. What does seem to need to be proven
is that the resulting contraption will run smoothly without
jamming (unless, perhaps, "jamming" is taken as "halting").
There is little doubt that this is a new computing scheme,
different from what has been seen before, even though it
contains fragments of earlier technologies. For that reason
I would not want to use the phrase "Turing Machine," even
though an important part of the construction consists in
showing that eventually and indirectly it can be made to
do what a Turing Machine does (or doesn't). So, much of the
ensuing discussion of whether Rule 110 *is* a Turing Machine
really depends on the degree that such a machine can be
duplicated, emulated, whatever, in a Post system, after the
latter has been rendered into a tag system, a cyclic tag
system, and whatever more is needed. But all that seems to
be reasonably well established.
Nevertheless, I would still like to see some of its (Cook's
machine) operating details clarified.
Kenneth Doyle
news:crrgk6$i6n$03$1...@news.t-online.com:
>> A Turing machine has infinite storage capacity. That seems to me to
>> be a more fundamental disqualifier for any physical machine. In any
>> event, it
>
> I don't think that it says that you must have infinite memory.
>I think
> the definition of a TM ist that you hav enough memory for the
> operation.
> If you need only 6kByte than you construct a TM with a Type
> that contains only that amount of memory. If you want to calculate the
> numbers of Pi you need infinite memory.
>
But we don't always know how much memory might be required by some series
of calculations. It seems to me to be just an extended version of the
halting problem. Knowing whether or not a calculation requires a finite
amount of memory, is implied in knowing how much memory it requires; and it
only requires an infinite amount of memory if the calculation never
terminates. Therefore, knowing how much (finite) memory a calculation will
require implies knowing that the calculation will terminate.