Computing Fibonacci numbers on a Turing Machine
Alex Vinokur
Is there any program of computing Fibonacci numbers on a Turing Machine?
Thanks,
==========================================
Alex Vinokur
mailto:ale...@connect.to
http://www.simtel.net/pub/oth/19088.html
http://sourceforge.net/users/alexvn
==========================================
Hans Aberg
<ale...@connect.to> wrote:
>Is there any program of computing Fibonacci numbers on a Turing Machine?
Many computer programming languages are known to be Turing complete (e.g.
TeX :-)), so just take any program in your favorite Turing complete
language.
If you want a program in a real Turing machine, all you have to do is to
pretend that your computer has an infinite amount of memory: No real
computer is a Turing machine, as it does not have an infinite amount of
memory.
Hans Aberg * Anti-spam: remove "remove." from email address.
* Email: Hans Aberg <remove...@member.ams.org>
* Home Page: <http://www.math.su.se/~haberg/>
* AMS member listing: <http://www.ams.org/cml/>
Richard Wheeldon
> Is there any program of computing Fibonacci numbers on a Turing Machine?
Try the brainfuck source - it should be an easy matter to
convert it. e.g :
http://www.hevanet.com/cristofd/brainfuck/fib.b
Richard
Daniel.
Maybe. But brainfuck isn't really that similar to a Turing machine--it
just uses the same memory model. I think it might perhaps be easier to
design one from scratch. Question one is, do you want them calculated
in unary, binary, octal, decimal, hexadecimal, or what? Unary would
probably be easiest and yield the simplest Turing machine...I think
I'll have a shot at that now in fact.
-Daniel Cristofani.
Daniel.
> pretend that your computer has an infinite amount of memory: No real
> computer is a Turing machine, as it does not have an infinite amount of
> memory.
But "Turing Machine" doesn't usually mean the same thing as
"Turing-complete machine". Usually it means something very similar to
the machine described in Turing's original paper, not merely something
having equivalent computational power.
-Daniel Cristofani.
Mark A. Biggar
> If you want a program in a real Turing machine, all you have to do is to
> pretend that your computer has an infinite amount of memory: No real
> computer is a Turing machine, as it does not have an infinite amount of
> memory.
This is a common misconception. A Turing Machine does not have an
infinite memory; It has an unbounded memory. An unbounded memory
is finite at all time, it can just grow as large as needed. A modern
computer with an external IO unit, like a tape or floppy drive, also
has an unbounded memory (as long as you can supply more tapes or
floppies!)
Insisting on a real infinite memory is no more reasonable then insisting
that you can wait until a non-terminating process ends. Actually, given
that a TM can only access a finite amount of its tape in a finite time,
those (infinite memory vs infinite time) are exactly the same.
Daniel.
sequence. (In fact, the ability to halt was not a feature of the
Turing machine in its original form.) We'll use letters instead of
numbers for the tape symbols, for clarity; we want to produce the
Fibonacci sequence in unary on the tape, like
ooioioiioiiioiiiiioiiiiiiiio... We'll assume the tape is full of
ooooo... originally. We'll need a third symbol a for keeping track of
where we are--the i's will be turned into a's and back while copying
them. the sequence of events while adding (say) 5 and 8 to get 13 will
be something like:
ooioioiioiiioaaaaaoiiiiiiiioooooooooooooooooooooo...
ooioioiioiiioaaaaaoiiiiaaaaoiiiiooooooooooooooooo...
ooioioiioiiioaaaaaoaaaaaaaaoiiiiiiiiooooooooooooo...
ooioioiioiiioaaiiioaaaaaaaaoiiiiiiiiiiioooooooooo...
ooioioiioiiioiiiiioaaaaaaaaoiiiiiiiiiiiiioooooooo...
This machine uses 16 states, and the head does not go farther left
than its starting point. It has an "inner loop" running through states
4 5 6 7 4, while copying the most recent number and turning it to a's
in its original location; another "inner loop" running through states
8 9 10 11 12 13 8, while adding the second-most-recent number onto
this copy, and turning it from a's to i's in its original location;
and an "outer loop" running through 4 8 14 15 16 4, which does both
the inner loops and then moves the head to the end of the new number
to repeat the process.
1 o o > 2
2 o o > 3
3 o i > 7 initialization--drop into state 7 as a shortcut to 4
4 a a < 4 scan left through second number to an i and change it to a
4 i a > 5
4 o o < 8 (done with second number--exit 4 5 6 7 4 loop)
5 a a > 5 scan right through second number
5 o o > 6
6 i i > 6 scan right to end of result and add an i
6 o i < 7
7 i i < 7
7 o o < 4 scan left through result to second number
8 i i < 8 scan left through first number to an a and change it to i
8 a i > 9
8 o o > 14 (done with first number--exit 8 9 10 11 12 13 8 loop)
9 i i > 9 scan right through first number
9 o o > 10
10 a a > 10 scan right through second number
10 o o > 11
11 i i > 11 scan right to end of result and add an i
11 o i < 12
12 i i < 12 scan left through result
12 o o < 13
13 a a < 13 scan left through second number to first number
13 o o < 8
14 i i > 14 scan right through first number
14 o o > 15
15 a a > 15 scan right through second number
15 o o > 16
16 i i > 16 scan right through result, which now becomes new "second
number"
16 o o < 4
This is just a very "dumb", straightforward machine to do the job.
Probably it can be done with a smaller machine, but I don't want to
bother.
-Daniel Cristofani.
tc...@lsa.umich.edu
Mark A. Biggar <ma...@biggar.org> wrote:
>Hans Aberg wrote:
>> If you want a program in a real Turing machine, all you have to do is to
>> pretend that your computer has an infinite amount of memory: No real
>> computer is a Turing machine, as it does not have an infinite amount of
>> memory.
>
>This is a common misconception. A Turing Machine does not have an
>infinite memory; It has an unbounded memory. An unbounded memory
>is finite at all time, it can just grow as large as needed. A modern
>computer with an external IO unit, like a tape or floppy drive, also
>has an unbounded memory (as long as you can supply more tapes or
>floppies!)
You're being unnecessarily pedantic. Whether the memory is "unbounded" or
"infinite," no real computer has it. No real computer even has a measly
10^(10^100) bits of memory.
Furthermore, the set of computable functions is unchanged whether the
memory is "unbounded" or "infinite." So there's little point in being
emphatic about the distinction.
--
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
Mark A. Biggar
> In article <DxsJa.64148$Fa6.43669@sccrnsc02>,
> Mark A. Biggar <ma...@biggar.org> wrote:
>
>>Hans Aberg wrote:
>>
>>>If you want a program in a real Turing machine, all you have to do is to
>>>pretend that your computer has an infinite amount of memory: No real
>>>computer is a Turing machine, as it does not have an infinite amount of
>>>memory.
>>
>>This is a common misconception. A Turing Machine does not have an
>>infinite memory; It has an unbounded memory. An unbounded memory
>>is finite at all time, it can just grow as large as needed. A modern
>>computer with an external IO unit, like a tape or floppy drive, also
>>has an unbounded memory (as long as you can supply more tapes or
>>floppies!)
>
>
> You're being unnecessarily pedantic.
But you have to be "pedantic" if you want to stop arguments like the
above that a TM is not a good abstract model for a real computer.
> Whether the memory is "unbounded" or
> "infinite," no real computer has it. No real computer even has a measly
> 10^(10^100) bits of memory.
Yes, but we're not willing to wait for a computer to execute that many
instructions either. So there's no real difference.
> Furthermore, the set of computable functions is unchanged whether the
> memory is "unbounded" or "infinite." So there's little point in being
> emphatic about the distinction.
The distinction is important, as unbounded memory allows for using a TM
as an abstract model for a real computer, where infinite memory does
not.
tc...@lsa.umich.edu
Mark A. Biggar <ma...@biggar.org> wrote:
>>>Hans Aberg wrote:
>>>>If you want a program in a real Turing machine, all you have to do is to
>>>>pretend that your computer has an infinite amount of memory: No real
>>>>computer is a Turing machine, as it does not have an infinite amount of
>>>>memory.
>But you have to be "pedantic" if you want to stop arguments like the
>above that a TM is not a good abstract model for a real computer.
Hans Aberg did not argue that a TM is not a *good abstract model* for a real
computer. He just said that no real computer is a Turing machine, which is
true, regardless of whether the memory is "unbounded" or "infinite."
And in any case, even a Turing machine with an infinite amount of memory
can easily be defended as a reasonable model by pointing out that only
a finite amount of it is used at any time.
>The distinction is important, as unbounded memory allows for using a TM
>as an abstract model for a real computer, where infinite memory does not.
Sure it does. An abstract model need not be exactly the same as the real
thing; it just has to be similar *enough*. A TM with infinite memory is
plenty similar enough to serve as a model.
Anyway, my main objection is to your calling it a "misconception" that
TM's have infinite memory. For starters, that happens to be exactly how
it's defined in many texts. And the other thing is that the model comes
out to be exactly the same whether you choose to call the memory "unbounded"
or "infinite," so why bother pounding on the distinction?
Linnea
>
> Insisting on a real infinite memory is no more reasonable then insisting
> that you can wait until a non-terminating process ends. Actually, given
> that a TM can only access a finite amount of its tape in a finite time,
> those (infinite memory vs infinite time) are exactly the same.
I would also like to remind that although we are mostly interested
in those Turing machines that do halt, not every Turing machine does.
On the other hand, we have no effective algorithm to recognize which do,
so we need a model which covers all of the programs we try to write,
whether they stop or not.
The difference between the abstract model and the real computers is that
when it really comes to infinity of computation, all real computers
appear very much bounded.
--
Linnea
Hans Aberg
cris...@hevanet.com (Daniel.) wrote:
My impression of this Turing's theory was that he defined a class of
abstract (logical) machines, each called an "Turing machine", the point
being that all of them can compute the same things.
Most real world computers, if they had an infinite amount of memory
accessible, would be Turing machines.
In article <3ef724f6$0$3945$b45e...@senator-bedfellow.mit.edu>,
tc...@lsa.umich.edu wrote:
>In article <NpEJa.70343$Fa6.46428@sccrnsc02>,
>Mark A. Biggar <ma...@biggar.org> wrote:
>>>>Hans Aberg wrote:
>>>>>If you want a program in a real Turing machine, all you have to do is to
>>>>>pretend that your computer has an infinite amount of memory: No real
>>>>>computer is a Turing machine, as it does not have an infinite amount of
>>>>>memory.
>[...]
>>But you have to be "pedantic" if you want to stop arguments like the
>>above that a TM is not a good abstract model for a real computer.
>
>Hans Aberg did not argue that a TM is not a *good abstract model* for a real
>computer. He just said that no real computer is a Turing machine, which is
>true, regardless of whether the memory is "unbounded" or "infinite."
>
>And in any case, even a Turing machine with an infinite amount of memory
>can easily be defended as a reasonable model by pointing out that only
>a finite amount of it is used at any time.
Thank you. Now I get to know what I really meant. :-)
Actually, the Turing machine, an abstract logical concept, is not a very
good model for a real world computer: It only captures one aspect of the
real world computers.
Namely, we know that a real world computer can never compute more than a
Turing machine. But usually, much less, as one runs out of memory, as
anybody with a crammed hard disk knows. :-)
Even though real world computers are restrictions of Turing machines that
have a finite amount of memory when viewed as an isolated system, when
hooked up to the real world, that new combined system do not anymore
behave as a Turing machine. For example, if you hook up a keyboard and put
a human at the keyboard, if one you believes that humans are not
restrictions of Turing machines, that combined system can do things that a
Turing machine cannot do. If you do not like that setup, attach a QM
(quantum mechanical) random number generator to your computer, and that
combined system is certainly not a Turing machine restriction as due to
the Heisenberg uncertainty principle valid in QM but not in Turing
machines where everything is deterministic.
Another aspect that the Turing machine models fails to take into account
is the time it takes to compute: If it takes a long time, then it is not
any practical, even though it is computable. This is a practical problem
in connection with the structure of data processed Turing model fails to
capture. For example, even if you know that arbitrary precision Fibonacci
numbers can be computed in TeX, if that language now is Turing complete,
are you sure you can print it out in a human readable form? -- The Turing
completeness probably only means that somehow a Turing kernel can
isolated, and that does not necessarily tell whether the same generality
applies when hooking it up to the output system. And do you have time for
waiting for the result if that would be say a million times slower than in
C?
So the Turing machine is very important theoretical concept as it tells
what a computer cannot do as an isolated algorithmic machinery. But it is
not a very good model for real world computers, as there are many other
important aspect to take into account.
In article <3ef6feb8$0$3929$b45e...@senator-bedfellow.mit.edu>,
tc...@lsa.umich.edu wrote:
>In article <DxsJa.64148$Fa6.43669@sccrnsc02>,
>Mark A. Biggar <ma...@biggar.org> wrote:
>>Hans Aberg wrote:
>>> If you want a program in a real Turing machine, all you have to do is to
>>> pretend that your computer has an infinite amount of memory: No real
>>> computer is a Turing machine, as it does not have an infinite amount of
>>> memory.
>>
>>This is a common misconception. A Turing Machine does not have an
>>infinite memory; It has an unbounded memory. An unbounded memory
>>is finite at all time, it can just grow as large as needed. A modern
>>computer with an external IO unit, like a tape or floppy drive, also
>>has an unbounded memory (as long as you can supply more tapes or
>>floppies!)
>
>You're being unnecessarily pedantic. Whether the memory is "unbounded" or
>"infinite," no real computer has it. No real computer even has a measly
>10^(10^100) bits of memory.
>
>Furthermore, the set of computable functions is unchanged whether the
>memory is "unbounded" or "infinite." So there's little point in being
>emphatic about the distinction.
One might compare with the situation between mathematics and
metamathematics (= metalogic, proof theory, mathematical logic).
Then, mathematicians first hoped to develop a finitistic metamathematical
system which would be used to describe infinities. But it turns out that
it cannot be done that way. So the logic of the metamathematics in fact
assumes infinities and the induction axiom. This is then used in order to
study the induction axiom in number theory. :-)
One might though make a distinction: The infinities in metamathematics
might be described as "potentially infinite" (or "potentially unbounded"):
One assumes the belief that to any finite collection of say variables, one
can find another variable not in the set. This is essentially the Turing
machine assumption of "infinite memory". This is also how say a real world
computer program would be developed in say Prolog, but hopefully with some
safeguard when memory is full. (We might "demonstrate" this belief, if
variable names may have arbitrary lenght; we could then use x, xx, xxx,
... as variables. This would work if we had an infinite amount of paper,
which of course we don't in the real world.)
But once one has some such infinity, one can forget about the original
cautious belief and go haywire with (countable) infinities: For example,
demanding that very Turing machine is realized within some variation of
axiomatic set theory. (I figure that constructing the set of all Turing
machines would probably require the axiom of choice for an uncountable
cardinality.)
So ultimately, it barks down to whether you believe that infinities can
exist as logical objects.
Linnea
>
> My impression of this Turing's theory was that he defined a class of
> abstract (logical) machines, each called an "Turing machine", the point
> being that all of them can compute the same things.
You are probably confusing Turing machines with universal Turing
machines. Not every TM is universal.
--
Linnea
Daniel.
> >> pretend that your computer has an infinite amount of memory: No real
> >> computer is a Turing machine, as it does not have an infinite amount of
> >> memory.
>
> >But "Turing Machine" doesn't usually mean the same thing as
> >"Turing-complete machine". Usually it means something very similar to
> >the machine described in Turing's original paper, not merely something
> >having equivalent computational power.
>
> My impression of this Turing's theory was that he defined a class of
> abstract (logical) machines, each called an "Turing machine", the point
> being that all of them can compute the same things.
Your impression is half-right. He defined a particular kind of
abstract machine; he intended it to be able to compute anything
computable; and it in turn implicitly defines a class of computational
models with equivalent power. Turing proved that Church's lambda
calculus was in this class. However, "Turing machine" means the
original kind of machine defined by Turing, or a lightly revised
version of it, not any computational model of equivalent power.
Computational models of equivalent power are instead called
"Turing-complete". A Turing machine has some distinctive features,
e.g. it uses a one-dimensional tape for memory, and its only "state"
other than the tape is in the form of a single integer.
> Most real world computers, if they had an infinite amount of memory
> accessible, would be Turing machines.
No, they would be Turing-complete. Which is what's important anyway.
> If you do not like that setup, attach a QM
> (quantum mechanical) random number generator to your computer, and that
> combined system is certainly not a Turing machine restriction as due to
> the Heisenberg uncertainty principle valid in QM but not in Turing
> machines where everything is deterministic.
Depending on whether the uncertainty principle describes indeterminacy
of events, or just a limitation on how precisely we can measure them.
Different interpretations of QM vary on this point.
> (I figure that constructing the set of all Turing
> machines would probably require the axiom of choice for an uncountable
> cardinality.)
I would like to see that supported. Turing machines are not that hard
to enumerate. Though maybe this leads back to the confusion about the
definition.
-Daniel Cristofani.
Hans Aberg
>> Most real world computers, if they had an infinite amount of memory
>> accessible, would be Turing machines.
>
>No, they would be Turing-complete. Which is what's important anyway.
Sorry for the mixup: I am forced to look up the formal theory of Turing
computability.
There is a formal definition of a Turing machine T.
>> (I figure that constructing the set of all Turing
>> machines would probably require the axiom of choice for an uncountable
>> cardinality.)
>
>I would like to see that supported. Turing machines are not that hard
>to enumerate. Though maybe this leads back to the confusion about the
>definition.
Right. The set of Turing machines are easily enumerated.
A function f is called Turing computable if there is a Turing machine T
that can compute it. But different f can have different T in this
definition.
This my source does not however mention "Universal Turing machines", which
I gather would be one that can compute all algorithms, or one which is
Turing-complete.
Then one can show that various classes of computabiliy are the same,
Turing computable, partially Markov-computable, etc.
>> If you do not like that setup, attach a QM
>> (quantum mechanical) random number generator to your computer, and that
>> combined system is certainly not a Turing machine restriction as due to
>> the Heisenberg uncertainty principle valid in QM but not in Turing
>> machines where everything is deterministic.
>
>Depending on whether the uncertainty principle describes indeterminacy
>of events, or just a limitation on how precisely we can measure them.
>Different interpretations of QM vary on this point.
There are two hurdles if you want to make a QM system into a Turing machine:
First, QM waves (states) makes use of the set of complex numbers, which in
description is an uncountable set. QM itself can of course be describe by
a finite set of symbols, so it might be possible to get around this point
on the meta level.
Even if you get around this problem and make a fully deterministic QM
description of your QM machine, which is possible, there is no way, by the
Heisenberg uncertainty principle, to measure its states down in order to
predict is computations: The QM states are not measurable quantities,
simply.
By contrast, people imagine that it is possible to measure down the states
of a Turing machine. In reality though, there is a small probability for
any measurement to go wrong, again by QM.
This is a fact that has played a role in the design of computers: Strictly
speaking, there is a QM probability that any CPU computation goes wrong,
so in the design of a computer, one tries to minimize the chance for it
happening.
I think this is an interesting point when dealing with logical theories,
such as the Turing machine then, because strictly speaking all logic is
just a mind work (with no strict realization in the physical world), used
because it turns out to be suitable in describing the real, physical
world. Sometimes, when discussing such matters, one gets the feeling that
people think that logic and logical theories are something more than that.
Kent Paul Dolan
> cris...@hevanet.com (Daniel.) wrote:
>> hab...@matematik.su.se (Hans Aberg) wrote:
> This my source does not however mention "Universal Turing
> machines", which I gather would be one that can compute
> all algorithms, or one which is Turing-complete.
If I recall correctly, a UTM is a TM which can emulate the
operation of any other TM [at the usual huge cost in run
time increase], essentially given a tape encoding both that
other TM's rules and its input data.
Nope. A TM is a _conceptual_ entity, not one enmeshed in the
real physical world, and the uncertainty principle doesn't
have any bearing on conceptual entities. It is worth noting
that this confusion has occurred repeatedly in this thread.
Real world physical limitations simply do not apply to TMs,
even in concept.
> This is a fact that has played a role in the design of
> computers: Strictly speaking, there is a QM probability
> that any CPU computation goes wrong,
Only for a physical computer, but there it is much more than
just a concept: Cray One #1 failed to be useful as more than
a prototype to be installed until a working version was
delivered, simply because it didn't have error correcting
memory, and the alpha partical emissions of its own circuit
components were enough to limit its error free operation to
something on the order of 90 minutes, far less than the time
needed to solve its typical target problem.
> so in the design of a computer, one tries to minimize the
> chance for it happening.
Umm, no, for that is impossible. One includes components to
_compensate_ for it happening, in particular error detecting
and error correcting hardware or software or usually both.
> I think this is an interesting point when dealing with
> logical theories, such as the Turing machine then, because
> strictly speaking all logic is just a mind work (with no
> strict realization in the physical world), used because it
> turns out to be suitable in describing the real, physical
> world. Sometimes, when discussing such matters, one gets
> the feeling that people think that logic and logical
> theories are something more than that.
What seems strange to me is that you imply they are
something _less_ than that, in particular, that they are
subject to physical limitations, rather than just
mathematical ones.
xanthian.
Daniel.
> This my source does not however mention "Universal Turing machines", which
> I gather would be one that can compute all algorithms, or one which is
> Turing-complete.
That's the definition I would use, yes. There seem to be two versions
of the concept:
A. A UTM is a Turing machine that can simulate the operation of any
Turing machine acting on any input.
B. A UTM is a Turing machine that can DIRECTLY simulate the operation
of any Turing machine acting on any input.
So a UTM in sense B expects to be given a description of a Turing
machine's state table and input; whereas a UTM in sense A expects a
description of a computation to perform, but it might be in some
totally different format.
The distinction becomes relevant because you can construct much
smaller UTMs (in sense A) by simulating a computational model other
than the Turing machine. Marvin Minsky and some others used a model
called the Post tag system, resulting in a machine using four states
and six symbols; there have been claims of even smaller UTMs, but I
haven't seen details. Naturally these are not UTMs in sense B, since
they directly simulate tag systems and not Turing machines--but they
can simulate any Turing machine by simulating a tag system that
simulates that Turing machine, so they're UTMs in sense A. I would be
inclined to use sense A, as you have, partly because it avoids the
question of which representations are "direct".
> >> If you do not like that setup, attach a QM
> >> (quantum mechanical) random number generator to your computer, and that
> >> combined system is certainly not a Turing machine restriction as due to
> >> the Heisenberg uncertainty principle valid in QM but not in Turing
> >> machines where everything is deterministic.
> >
> >Depending on whether the uncertainty principle describes indeterminacy
> >of events, or just a limitation on how precisely we can measure them.
> >Different interpretations of QM vary on this point.
>
> There are two hurdles if you want to make a QM system into a Turing machine:
>
> First, QM waves (states) makes use of the set of complex numbers, which in
> description is an uncountable set. QM itself can of course be describe by
> a finite set of symbols, so it might be possible to get around this point
> on the meta level.
>
> Even if you get around this problem and make a fully deterministic QM
> description of your QM machine, which is possible, there is no way, by the
> Heisenberg uncertainty principle, to measure its states down in order to
> predict is computations: The QM states are not measurable quantities,
> simply.
Agreed. I think the question needs clarifying.
1. Given a computer combined with a quantum random number generator,
can we construct a Turing machine that will simulate it perfectly? No,
because of fundamental limitations on what we can measure, as you say.
2. Is a computer combined with a quantum random number generator
capable of producing a sequence of numbers that's not
Turing-computable, i.e. one that no Turing machine could output? No,
because any finite number sequence can be output by some Turing
machine, and the computer won't last forever.
3. The interesting question is whether the state of the physical
universe is Turing-computable. I don't think we really know the answer
to that one. What we can say is that it isn't computable by anyone in
the universe.
> I think this is an interesting point when dealing with logical theories,
> such as the Turing machine then, because strictly speaking all logic is
> just a mind work (with no strict realization in the physical world), used
> because it turns out to be suitable in describing the real, physical
> world.
Either that, or because it's fun.
-Daniel.
Daniel.
> operation of any other TM [at the usual huge cost in run
> time increase], essentially given a tape encoding both that
> other TM's rules and its input data.
Yes, but see my response to the previous post.
> Nope. A TM is a _conceptual_ entity, not one enmeshed in the
> real physical world, and the uncertainty principle doesn't
> have any bearing on conceptual entities. It is worth noting
> that this confusion has occurred repeatedly in this thread.
> Real world physical limitations simply do not apply to TMs,
> even in concept.
Agreed as regards the current concept of the Turing machine. It's
worth noting that physical realizability (in principle) was important
to Turing, though.
> > so in the design of a computer, one tries to minimize the
> > chance for it happening.
>
> Umm, no, for that is impossible. One includes components to
> _compensate_ for it happening, in particular error detecting
> and error correcting hardware or software or usually both.
One can do both. Better shielding and better components can reduce the
initial incidence of errors. Probably the issue is about the word
"minimize"--does it mean "reduce as much as is practical", or "reduce
to negligibility"?
-Daniel.
Hans Aberg
xant...@well.com (Kent Paul Dolan) wrote:
>> Even if you get around this problem and make a fully
>> deterministic QM description of your QM machine, which is
>> possible, there is no way, by the Heisenberg uncertainty
>> principle, to measure its states down in order to predict
>> is computations: The QM states are not measurable
>> quantities, simply.
>
>> By contrast, people imagine that it is possible to measure
>> down the states of a Turing machine. In reality though,
>> there is a small probability for any measurement to go
>> wrong, again by QM.
>
>Nope. A TM is a _conceptual_ entity, not one enmeshed in the
>real physical world, and the uncertainty principle doesn't
>have any bearing on conceptual entities. It is worth noting
>that this confusion has occurred repeatedly in this thread.
>Real world physical limitations simply do not apply to TMs,
>even in concept.
There is an intricate interplay between theory and the real physical world:
Logic in general and Turing machines in particular would be useless if
these theories could not be used in the description of some aspects of the
physical world we live in. (So a logic statement can not only be true or
false, it can also be useless. :-) )
In the case of Turing machines, those were constructed in view of the
development of computers. The theory of computabiliy shows that under some
theoretical idealization assumptions, one cannot go any further.
The same thing happens if one tries to make a model of a QM machine: One
would expect that it to be an idealization of something that can exist in
the real QM world.
In fact, there is not problem of making physical theories just for their
own sake: This is done so extensively in contemporary physics that
physicists themselves cannot tell whether a theory is to be vied valid or
a hoax. (Check out the newsgroup sci.physics.research late last year about
such a hoax.) Such developments may be of interest if that is fit into the
context of eventually creating a "verified" physical theory.
The same thing applies to a theory of machines, be it QM or Turing or whatever.
>> This is a fact that has played a role in the design of
>> computers: Strictly speaking, there is a QM probability
>> that any CPU computation goes wrong,
...
>> so in the design of a computer, one tries to minimize the
>> chance for it happening.
>
>Umm, no, for that is impossible. One includes components to
>_compensate_ for it happening, in particular error detecting
>and error correcting hardware or software or usually both.
It is impossible to actually attain a minimum, as the probability will
always stay > 0. But one can minimize it in the sense of lowering the
probability by say increasing the separation between the 1 and 0 states as
stored in the computer.
For example, I recall that one method to detect errors in the CPU
computation is to leave a lot of word instruction values unused: If such
an unused value shows up as an instruction value, then there must be an
error, and the CPU can call an error recovery routine.
I am not sure that this method is used anymore: Perhaps CPU's are so
secure that it is not needed.
One can lower the probabilities to the level they are "secure" if one
defines what "secure" means. For example, there is a probability that the
oxygen molecules where you breathe by chance assemble somewhere else so
that you by that choke to death. But the probability for that occurring is
so low that it probably will not happen within the lifespan of the known
universe.
If figure that if one plays this game in computer design, one will find
making a computer more safe adds to its cost. So eventually, one will
settle for something that is commercially feasible.
>> I think this is an interesting point when dealing with
>> logical theories, such as the Turing machine then, because
>> strictly speaking all logic is just a mind work (with no
>> strict realization in the physical world), used because it
>> turns out to be suitable in describing the real, physical
>> world. Sometimes, when discussing such matters, one gets
>> the feeling that people think that logic and logical
>> theories are something more than that.
>
>What seems strange to me is that you imply they are
>something _less_ than that, in particular, that they are
>subject to physical limitations, rather than just
>mathematical ones.
The theories are not subject to physical limitations, other than they must
be stored somewhere, like in the brain of a human, in a computer, on paper
or clay tablets, etc.
But experience has it that logical (mathematical) theories, if they should
be of any interest, must have some kind of interaction with the physical
world, otherwise that interest will eventually drop. That connection could
be very long distance, but tracing history of such histories usually
reveals what the connection to the physical world is. And later, a logic
theory can find new interactions with the physical world. A classical
example is perhaps the theories of Boole, which were unnoticed until
modern computers were invented. I gather logic itself is based on
experience in the physical, non-QM world that we live in.
So if you say the Turing machines are purely logical constructs with no
relation to the physical world either directly or indirectly via other
theories that have such a connection, why bother? -- If that would be the
case, then it can't have any meaning for what one is doing in computing,
for example.
Kent Paul Dolan
these are the most clearly expressed ones):
1) No one studies abstractions for their own sakes:
> Logic in general and Turing machines in particular would be useless if
> these theories could not be used in the description of some aspects of the
> physical world we live in.
> In the case of Turing machines, those were constructed in view of the
> development of computers. The theory of computabiliy shows that under some
> theoretical idealization assumptions, one cannot go any further.
2) No one studies things that can't be physically realized for their
own sakes:
> But experience has it that logical (mathematical) theories, if they should
> be of any interest, must have some kind of interaction with the physical
> world, otherwise that interest will eventually drop.
3) No one studies logical constructs without a physical world goal:
> So if you say the Turing machines are purely logical constructs with no
> relation to the physical world either directly or indirectly via other
> theories that have such a connection, why bother?
And yet almost all of "pure" mathematics is studied for the love of
working with those abstractions, and if a real world application
eventually is found, more often than not it is found by someone else,
so your thesis is entirely false. In any case, it gives no
justification for attempting to apply "the uncertainty principle" to
abstractions which have no physical component, my original demurrer.
> It is impossible to actually attain a minimum, as the probability will
> always stay > 0. But one can minimize it in the sense of lowering the
> probability by say increasing the separation between the 1 and 0 states as
> stored in the computer.
You have some _vast_ confusion about how much information one bit can
contain.
> For example, I recall that one method to detect errors in the CPU
> computation is to leave a lot of word instruction values unused: If such
> an unused value shows up as an instruction value, then there must be an
> error, and the CPU can call an error recovery routine.
"Brute stupidity" is indeed no longer used much, simply because it is
very expensive to have an operand lookup table most of whose possible
entries are invalid operations. You'd do well to do some reading on
"computer memory error detecting and correcting codes".
xanthian.
Hans Aberg
>hab...@matematik.su.se (Hans Aberg) wrote (more times than this, but
>these are the most clearly expressed ones):
>
>1) No one studies abstractions for their own sakes:
>2) No one studies things that can't be physically realized for their
>own sakes:
>3) No one studies logical constructs without a physical world goal:
I have not said anything like that. Logical theories are usually developed
in some kind of context, and tracing back that context historically, one
can usually see what the connections to the physical world are.
That is not very hard in the case of Turing machines though, since one
clearly, in view of the developments of computers, wanted to pin down the
notion of computability. Turing had one of largely equivalent approaches.
(Check "Church's Thesis".)
>> So if you say the Turing machines are purely logical constructs with no
>> relation to the physical world either directly or indirectly via other
>> theories that have such a connection, why bother?
>
>And yet almost all of "pure" mathematics is studied for the love of
>working with those abstractions, and if a real world application
>eventually is found, more often than not it is found by someone else,
>so your thesis is entirely false.
For example, Gauss discovered the rings Z/nZ when computing planet orbits,
and that is a part of modern developments of number theory. Number theory
has later become important in cryptology. Cantor discovered the ideas of
set theory when studying the exceptional sets of Fourier transforms, which
led to the development axiomatic set theory, and Fourier series are
important in describing various physical systems. Geometry was developed
from the need in Ancient Babylonia of measuring up arable land.
It is real hard to think about any mathematics whose context in a larger
sense is not derived from the physical world.
One might add that there was a pure math movement particularly in the late
mid 20th century (of which I once a part), that did a lot of mathematics
as abstractions with regards to any larger contexts, but I think it has
weakened, simply because of the strong development of computer technology.
> In any case, it gives no
>justification for attempting to apply "the uncertainty principle" to
>abstractions which have no physical component, my original demurrer.
We were discussing Turing machines, whose counterpart in the physical
world of which they are idealized abstractions are characterized by that
one tries to eliminate QM effects as far as that is practically possible.
In that context, the question of QM machines arose. The Heisenberg
uncertainty principle is an easy consequence of the QM postulates, the
latter which are used in all types of QM theories.
Are you suggesting that we should discuss QM machines which do not make
use of QM? That sounds as a rather deceptive labelling of a theory. :-)
>> It is impossible to actually attain a minimum, as the probability will
>> always stay > 0. But one can minimize it in the sense of lowering the
>> probability or error by say increasing the separation between the 1 and 0
>> states as stored in the computer.
>
>You have some _vast_ confusion about how much information one bit can
>contain.
This does not seem to be a very informative argument; it does not seem to
contain any facts to react to.
So how much information do you claim one bit can contain? :-)
>> For example, I recall that one method to detect errors in the CPU
>> computation is to leave a lot of word instruction values unused: If such
>> an unused value shows up as an instruction value, then there must be an
>> error, and the CPU can call an error recovery routine.
>
>"Brute stupidity" is indeed no longer used much, simply because it is
>very expensive to have an operand lookup table most of whose possible
>entries are invalid operations. You'd do well to do some reading on
>"computer memory error detecting and correcting codes".
Fitting this in the discussed context, are you claiming that if a CPU is
not very accurate at computing the right instructions due to signal noise,
that can easily be compensated for by the use of error correcting codes?
Alex Vinokur
"Daniel." <cris...@hevanet.com> wrote in message news:474b22da.03062...@posting.google.com...
> Okay. A nonterminating machine seems cleanest for a nonterminating
> sequence. (In fact, the ability to halt was not a feature of the
> Turing machine in its original form.) We'll use letters instead of
> numbers for the tape symbols, for clarity; we want to produce the
> Fibonacci sequence in unary on the tape, like
> ooioioiioiiioiiiiioiiiiiiiio... We'll assume the tape is full of
> ooooo... originally. We'll need a third symbol a for keeping track of
> where we are--the i's will be turned into a's and back while copying
> them. the sequence of events while adding (say) 5 and 8 to get 13 will
> be something like:
>
> ooioioiioiiioaaaaaoiiiiiiiioooooooooooooooooooooo...
> ooioioiioiiioaaaaaoiiiiaaaaoiiiiooooooooooooooooo...
> ooioioiioiiioaaaaaoaaaaaaaaoiiiiiiiiooooooooooooo...
> ooioioiioiiioaaiiioaaaaaaaaoiiiiiiiiiiioooooooooo...
> ooioioiioiiioiiiiioaaaaaaaaoiiiiiiiiiiiiioooooooo...
>
> This machine uses 16 states, and the head does not go farther left
> than its starting point. It has an "inner loop" running through states
> 4 5 6 7 4, while copying the most recent number and turning it to a's
> in its original location; another "inner loop" running through states
> 8 9 10 11 12 13 8, while adding the second-most-recent number onto
> this copy, and turning it from a's to i's in its original location;
> and an "outer loop" running through 4 8 14 15 16 4, which does both
> the inner loops and then moves the head to the end of the new number
> to repeat the process.
Hi Daniel,
I have used your Turing program on my C++ Simulator of a Turing Machine
http://sourceforge.net/projects/turing-machine
http://alexvn.freeservers.com/s1/turing.html
It works fine.
Thanks.
Do you have a Turing program that computes one Fibonacci number :
Input : n
Output : n-th Fibonacci number
?
Regards,
=====================================
Alex Vinokur
mailto:ale...@connect.to
http://mathforum.org/library/view/10978.html
=====================================
Phil Carmody
> In article <DxsJa.64148$Fa6.43669@sccrnsc02>,
> Mark A. Biggar <ma...@biggar.org> wrote:
>>Hans Aberg wrote:
>>> If you want a program in a real Turing machine, all you have to do is to
>>> pretend that your computer has an infinite amount of memory: No real
>>> computer is a Turing machine, as it does not have an infinite amount of
>>> memory.
>>
>>This is a common misconception. A Turing Machine does not have an
>>infinite memory; It has an unbounded memory. An unbounded memory
>>is finite at all time, it can just grow as large as needed. A modern
>>computer with an external IO unit, like a tape or floppy drive, also
>>has an unbounded memory (as long as you can supply more tapes or
>>floppies!)
>
> You're being unnecessarily pedantic.
No, he's being correctly pedantic.
> Whether the memory is "unbounded" or
> "infinite," no real computer has it. No real computer even has a measly
> 10^(10^100) bits of memory.
However, I can trivially store a sequence of 10^(10^100) consecutive
zeroes, for example, through the use of a sparse representation, or
other compression. Therefore a simple PC _can_ represent some tapes of
length of 10^(10^100). Many runtime tape states of many commonly met
turing programs have _incredibly_ low entropy density, and the concept
of simulating tapes larger than actual available memory in these cases
is perfectly feasible.
Phil
tc...@lsa.umich.edu
Phil Carmody <thefatphi...@yahoo.co.uk> wrote:
>> tchow wrote:
>> You're being unnecessarily pedantic.
>No, he's being correctly pedantic.
But why? I still don't see what difference it makes whether the Turing
machine memory is "unbounded" or "infinite." You get the same model of
computation either way, so who cares?
>> Whether the memory is "unbounded" or
>> "infinite," no real computer has it. No real computer even has a measly
>> 10^(10^100) bits of memory.
>
>However, I can trivially store a sequence of 10^(10^100) consecutive
>zeroes, for example, through the use of a sparse representation, or
>other compression.
This comment is irrelevant, since it remains true that no real computer even
has a measly 10^(10^100) bits of memory, let alone an "unbounded" memory.
Torkel Franzen
> But why? I still don't see what difference it makes whether the Turing
> machine memory is "unbounded" or "infinite."
It makes no difference whatever.
Mark A. Biggar
The difference is between a potential and an actual infinity.
An unbounded memory is finite at all finite times, which is exactly
the situation for a modern computer with an external tape or floppy
drive. The fact that letting its memory grow very very large is
impractical is real no different then the fact that some computations
can take very very large amounts of time for which it is impractical
to wait.
tc...@lsa.umich.edu
>> tc...@lsa.umich.edu writes:
>>>But why? I still don't see what difference it makes whether the Turing
>>>machine memory is "unbounded" or "infinite."
>> It makes no difference whatever.
>The difference is between a potential and an actual infinity.
Yes, I understand the distinction you're trying to draw, but I maintain
that it is a distinction without a difference. It doesn't matter in the
slightest whether the memory is "potentially" or "actually" infinite. You
get exactly the same model of computation.
>An unbounded memory is finite at all finite times, which is exactly
>the situation for a modern computer with an external tape or floppy drive.
And again, the argument from what modern computers are like doesn't make
sense either. A modern computer does not continually request more memory
without limit. You buy a computer with a drive, and that fixed amount of
memory is all it has to work with. The computer does not go out and buy
itself more and more external drives until you intervene to stop it. An
unbounded memory is no more "real" than an infinite memory.
Hans Aberg
tc...@lsa.umich.edu wrote:
>>>>But why? I still don't see what difference it makes whether the Turing
>>>>machine memory is "unbounded" or "infinite."
>>> It makes no difference whatever.
>>The difference is between a potential and an actual infinity.
>
>Yes, I understand the distinction you're trying to draw, but I maintain
>that it is a distinction without a difference. It doesn't matter in the
>slightest whether the memory is "potentially" or "actually" infinite. You
>get exactly the same model of computation.
There seems to be a difference between potentially and actually infinite:
When developing metamathematics, one must start with some logic in a kind
of belief system. One then starts with the potentially infinite variation
in form that to any finite set of identifiers or variables, one can always
find another one not within that set. These are then intuitive
metamathematical notions which do not have anything to do with the
"actual" infinities (and axiomatic set theory) that one is developing
given that metamathematics.
The potential infinities are then a metamathematical bootstrap used in
order to develop a theory about actual infinities, like via axiomatic set
theory. One cannot do with less, as finitistic metamathematics evidently
cannot describe the induction axiom and the axiom of choice.
As for Turing machines and related topics such as Church's lambda
calculus, one can take two approaches: One is that these notions belong to
the area of metamathematics, and then the concept should be "potentially
infinite". Or one can say that one is merely interested in Turing machines
as an idealized model for computers, to be realized within axiomatic set
theory. In this case, one view the whole paper strip (Turing machine
memory) at once as an actual infinity, if one so wishes.
Hans Aberg
<ma...@biggar.org> wrote:
>>>But why? I still don't see what difference it makes whether the Turing
>>>machine memory is "unbounded" or "infinite."
...
>> It makes no difference whatever.
>
>The difference is between a potential and an actual infinity.
>
>An unbounded memory is finite at all finite times, which is exactly
>the situation for a modern computer with an external tape or floppy
>drive.
No, an unbounded memory can always be extended, which is not the case with
a real computer: Already at 10^50--10^60 bits, one has exceeded the number
of atoms in the observable universe.
> The fact that letting its memory grow very very large is
>impractical is real no different then the fact that some computations
>can take very very large amounts of time for which it is impractical
>to wait.
The model of a potentially infinite memory is useful for practical
purposes as well, as if one stays within the limitations of time and
memory, one will know the results will come out the same. That is, if two
different computers are extended to both have sufficient memory, computing
the results within a reasonable amount of time, the results of the same
theoretical computation will come out the same.
But within any such theory of potentially unbounded memory, it is easy to
produce computations that will break any real life computer.
Marcel van Kervinck
> In article <pan.2003.06.27....@yahoo.co.uk>,
> Phil Carmody <thefatphi...@yahoo.co.uk> wrote:
>>> tchow wrote:
>>> You're being unnecessarily pedantic.
>>No, he's being correctly pedantic.
> But why? I still don't see what difference it makes whether the Turing
> machine memory is "unbounded" or "infinite." You get the same model of
> computation either way, so who cares?
It means the difference between the number of possible
states a tape can be in. An 'unbounded' tape could only
be in one of a countable infinite number of states. An
'unfinite tape' can be in one of a over-countable infinite
number of states (depending on how you allow the TM to
be initialized).
Marcel
-- _ _
_| |_|_|
|_ |_ mar...@bitpit.net
|_| Marcel van Kervinck
tc...@lsa.umich.edu
Marcel van Kervinck <mar...@brick.bitpit.net> wrote:
>It means the difference between the number of possible
>states a tape can be in. An 'unbounded' tape could only
>be in one of a countable infinite number of states. An
>'unfinite tape' can be in one of a over-countable infinite
>number of states (depending on how you allow the TM to
>be initialized).
Ah, well, if *this* is what was meant, then indeed there is a difference.
It is easily dealt with, of course, by explicitly saying that the
starting state of the tape cannot contain infinitely many non-blank
symbols. Still, if the argument is that defining the memory to be
unbounded rather than infinite removes all doubt as to whether the
tape can start with an infinite number of non-blank symbols, then I
concede that there is some merit to this argument. It then becomes
a matter of taste whether to call the memory unbounded or infinite.
(But I still think it is misguided to decree that an infinite memory
is a "misconception.")
Alex Vinokur
"Alex Vinokur" <ale...@bigfoot.com> wrote in message news:bd21po$oagok$1...@ID-79865.news.dfncis.de...
>
> Is there any program of computing Fibonacci numbers on a Turing Machine?
>
> Thanks,
>
Latest version of C++ Simulator of a Turing Machine (Version 1-0-3) performs several Turing programs.
One of them is "Computing a Fibonacci number".
http://sourceforge.net/projects/turing-machine
http://alexvn.freeservers.com/s1/turing.html
--------------------------------------------------
The program computes a Fibonacci number.
A number 'n' is represented by n 1-s.
Sample :
5 is represented as 1 1 1 1 1
3 is represented as 1 1 1
Input : number 'n'
Sample :
1 1 1 1 1 1 1
Output : Fibonacci#n
Sample :
1 1 1 1 1 1 1 1 1 1 1 1 1
--------------------------------------------------
--
==========================================
Alex Vinokur
mailto:ale...@connect.to
http://www.simtel.net/pub/oth/19088.html
http://sourceforge.net/users/alexvn
==========================================
Alex Vinokur
"Alex Vinokur" <ale...@bigfoot.com> wrote in message news:be9ibm$2lofp$1...@ID-79865.news.dfncis.de...
>
> "Alex Vinokur" <ale...@bigfoot.com> wrote in message news:bd21po$oagok$1...@ID-79865.news.dfncis.de...
> >
> > Is there any program of computing Fibonacci numbers on a Turing Machine?
> >
> > Thanks,
> >
>
> Latest version of C++ Simulator of a Turing Machine (Version 1-0-3) performs several Turing programs.
> One of them is "Computing a Fibonacci number".
> http://sourceforge.net/projects/turing-machine
> http://alexvn.freeservers.com/s1/turing.html
>
> --------------------------------------------------
> The program computes a Fibonacci number.
> A number 'n' is represented by n 1-s.
> Sample :
> 5 is represented as 1 1 1 1 1
> 3 is represented as 1 1 1
>
> Input : number 'n'
> Sample :
> 1 1 1 1 1 1 1
>
> Output : Fibonacci#n
> Sample :
> 1 1 1 1 1 1 1 1 1 1 1 1 1
> --------------------------------------------------
>
Raw Logs : http://groups.google.com/groups?th=1e653c4ef60faa44
=====================================
Alex Vinokur
mailto:ale...@connect.to
http://mathforum.org/library/view/10978.html
=====================================
Douglas Eagleson
> Is there any program of computing Fibonacci numbers on a Turing Machine?
>
> Thanks,
>
> Alex Vinokur
> mailto:ale...@connect.to
> http://www.simtel.net/pub/oth/19088.html
> http://sourceforge.net/users/alexvn
> ==========================================
The IBM research people just shifted an atom over
a set of stationary atoms! Making a computer from the
set.
And so the person is left with the proper means of
programming the little atom computer. So a good project
is to relate the set state to the computer state. Meaning
the abstract computer as Turing's Theory appears the correct
relation in this example.
And the idea of Turing's infinite state requirment is then only
a set's abstract necessity and not really necessary in a useful
working computer.
And the simple relation of the set to its cause is defined
by the little atom computers design.
So the shifted atom computes!
Meaning a project is to copy this new atom computer in
a software and learn to write the defined shift caused
set, without relation to the number of places the
atom jumped.
That is all the darn thing is! And your special sequence
may then be programmed correctly without mathematical
theory. Meaning, how is your special sequence related to
Turing's machine? Related independent of its mathematical
definition.
And so cryptography appears another subject.
How that?
Douglas Eagleson
Gaithersburg,MD USA
Alex Vinokur
Here is description of a Turing Machine which computes Fibonacci numbers.
%%============================================
%%============== Turing Machine ==============
%%======= Computing a Fibonacci number =======
%%======== Machine Definition : BEGIN ========
%%============================================
====== Description ======
Computing Fibonacci numbers.
The program computes a Fibonacci number.
A number 'n' is represented by n 1-s.
Sample :
5 is represented as 1 1 1 1 1
3 is represented as 1 1 1
Input : number 'n'
Sample (n = 7) :
1 1 1 1 1 1 1
Output : Fibonacci#n
Sample (Fibonacci#7) :
1 1 1 1 1 1 1 1 1 1 1 1 1
Created by Alex Vinokur <mailto:ale...@connect.to>
====== States ======
Initial state : q0
Halting state : qf
Internal states : q101 q102 q103 q104 q105 q106 q107 q108 q109 q201 q202 q203 q204 q301 q302 q303 q304 q305 q306 q307 q308 q309 q310
q311 q401 q402 q403 q404 q501 q502 q503 q601 q602 q603 q604 q701 q702 q703 q704 q801 q802 q803 q804 q805 q806 q807 q808 q809
====== Alphabet ======
Empty symbols alphabet : b
Input alphabet : 1
Internal alphabet : x *
====== Transition Table ======
Rule# 0 : q0 [ 1 ] ---> q101 [ (x, R) ]
Rule# 1 : q101 [ 1 ] ---> q101 [ (1, R) ]
Rule# 2 : q101 [ b ] ---> q102 [ (1, R) ]
Rule# 3 : q102 [ b ] ---> q103 [ (*, R) ]
Rule# 4 : q103 [ b ] ---> q104 [ (1, R) ]
Rule# 5 : q104 [ b ] ---> q601 [ (*, L) ]
Rule# 6 : q105 [ b ] ---> q106 [ (1, L) ]
Rule# 7 : q106 [ * ] ---> q701 [ (*, L) ]
Rule# 8 : q107 [ * ] ---> q108 [ (*, L) ]
Rule# 9 : q107 [ 1 ] ---> q107 [ (1, L) ]
Rule# 10 : q108 [ * ] ---> q109 [ (*, N) ]
Rule# 11 : q108 [ 1 ] ---> q108 [ (1, L) ]
Rule# 12 : q109 [ * ] ---> q109 [ (*, R) ]
Rule# 13 : q109 [ 1 ] ---> q109 [ (1, R) ]
Rule# 14 : q109 [ b ] ---> q201 [ (*, N) ]
Rule# 15 : q201 [ * ] ---> q202 [ (*, L) ]
Rule# 16 : q201 [ 1 ] ---> q201 [ (1, L) ]
Rule# 17 : q202 [ * ] ---> q203 [ (*, R) ]
Rule# 18 : q202 [ 1 ] ---> q202 [ (1, L) ]
Rule# 19 : q202 [ b ] ---> q203 [ (b, R) ]
Rule# 20 : q203 [ * ] ---> q301 [ (*, N) ]
Rule# 21 : q203 [ 1 ] ---> q204 [ (b, R) ]
Rule# 22 : q204 [ * ] ---> q204 [ (*, R) ]
Rule# 23 : q204 [ 1 ] ---> q204 [ (1, R) ]
Rule# 24 : q204 [ b ] ---> q201 [ (1, L) ]
Rule# 25 : q301 [ * ] ---> q302 [ (*, L) ]
Rule# 26 : q302 [ * ] ---> q303 [ (*, L) ]
Rule# 27 : q302 [ b ] ---> q302 [ (b, L) ]
Rule# 28 : q303 [ * ] ---> q304 [ (*, R) ]
Rule# 29 : q303 [ 1 ] ---> q303 [ (1, L) ]
Rule# 30 : q303 [ b ] ---> q304 [ (b, R) ]
Rule# 31 : q304 [ * ] ---> q308 [ (b, N) ]
Rule# 32 : q304 [ 1 ] ---> q305 [ (b, R) ]
Rule# 33 : q305 [ * ] ---> q306 [ (*, R) ]
Rule# 34 : q305 [ 1 ] ---> q305 [ (1, R) ]
Rule# 35 : q306 [ * ] ---> q307 [ (*, L) ]
Rule# 36 : q306 [ 1 ] ---> q307 [ (1, L) ]
Rule# 37 : q306 [ b ] ---> q306 [ (b, R) ]
Rule# 38 : q307 [ b ] ---> q302 [ (1, L) ]
Rule# 39 : q308 [ 1 ] ---> q309 [ (1, L) ]
Rule# 40 : q308 [ b ] ---> q308 [ (b, R) ]
Rule# 41 : q309 [ b ] ---> q310 [ (*, L) ]
Rule# 42 : q310 [ * ] ---> q311 [ (*, R) ]
Rule# 43 : q310 [ b ] ---> q310 [ (1, L) ]
Rule# 44 : q311 [ * ] ---> q501 [ (*, R) ]
Rule# 45 : q311 [ 1 ] ---> q311 [ (1, R) ]
Rule# 46 : q401 [ * ] ---> q402 [ (*, L) ]
Rule# 47 : q401 [ 1 ] ---> q401 [ (1, L) ]
Rule# 48 : q402 [ * ] ---> q403 [ (*, L) ]
Rule# 49 : q402 [ 1 ] ---> q402 [ (1, L) ]
Rule# 50 : q403 [ * ] ---> q403 [ (*, L) ]
Rule# 51 : q403 [ 1 ] ---> q404 [ (*, L) ]
Rule# 52 : q404 [ * ] ---> q404 [ (*, R) ]
Rule# 53 : q404 [ 1 ] ---> q404 [ (1, R) ]
Rule# 54 : q404 [ b ] ---> q201 [ (*, N) ]
Rule# 55 : q404 [ x ] ---> q801 [ (x, N) ]
Rule# 56 : q501 [ * ] ---> q502 [ (1, N) ]
Rule# 57 : q501 [ 1 ] ---> q501 [ (1, R) ]
Rule# 58 : q502 [ 1 ] ---> q502 [ (1, R) ]
Rule# 59 : q502 [ b ] ---> q503 [ (b, L) ]
Rule# 60 : q503 [ 1 ] ---> q401 [ (b, L) ]
Rule# 61 : q601 [ * ] ---> q602 [ (*, L) ]
Rule# 62 : q601 [ 1 ] ---> q601 [ (1, L) ]
Rule# 63 : q602 [ 1 ] ---> q603 [ (*, L) ]
Rule# 64 : q603 [ 1 ] ---> q604 [ (1, R) ]
Rule# 65 : q603 [ x ] ---> q801 [ (x, N) ]
Rule# 66 : q604 [ * ] ---> q604 [ (*, R) ]
Rule# 67 : q604 [ 1 ] ---> q604 [ (1, R) ]
Rule# 68 : q604 [ b ] ---> q105 [ (b, N) ]
Rule# 69 : q701 [ * ] ---> q702 [ (*, L) ]
Rule# 70 : q701 [ 1 ] ---> q701 [ (1, L) ]
Rule# 71 : q702 [ * ] ---> q702 [ (*, L) ]
Rule# 72 : q702 [ 1 ] ---> q703 [ (*, L) ]
Rule# 73 : q703 [ 1 ] ---> q704 [ (1, R) ]
Rule# 74 : q703 [ x ] ---> q801 [ (x, N) ]
Rule# 75 : q704 [ * ] ---> q704 [ (*, R) ]
Rule# 76 : q704 [ 1 ] ---> q704 [ (1, R) ]
Rule# 77 : q704 [ b ] ---> q107 [ (b, L) ]
Rule# 78 : q801 [ * ] ---> q801 [ (*, R) ]
Rule# 79 : q801 [ 1 ] ---> q801 [ (1, R) ]
Rule# 80 : q801 [ b ] ---> q802 [ (b, L) ]
Rule# 81 : q801 [ x ] ---> q801 [ (x, R) ]
Rule# 82 : q802 [ * ] ---> q808 [ (b, L) ]
Rule# 83 : q802 [ 1 ] ---> q808 [ (1, L) ]
Rule# 84 : q803 [ * ] ---> q803 [ (*, L) ]
Rule# 85 : q803 [ 1 ] ---> q803 [ (*, L) ]
Rule# 86 : q803 [ x ] ---> q804 [ (x, R) ]
Rule# 87 : q804 [ * ] ---> q804 [ (*, R) ]
Rule# 88 : q804 [ 1 ] ---> q805 [ (*, L) ]
Rule# 89 : q804 [ b ] ---> q809 [ (b, N) ]
Rule# 90 : q805 [ * ] ---> q805 [ (*, L) ]
Rule# 91 : q805 [ 1 ] ---> q806 [ (1, R) ]
Rule# 92 : q805 [ x ] ---> q806 [ (*, N) ]
Rule# 93 : q806 [ * ] ---> q807 [ (1, R) ]
Rule# 94 : q807 [ * ] ---> q804 [ (*, R) ]
Rule# 95 : q808 [ * ] ---> q803 [ (*, L) ]
Rule# 96 : q808 [ 1 ] ---> q808 [ (1, L) ]
Rule# 97 : q809 [ * ] ---> q809 [ (b, L) ]
Rule# 98 : q809 [ 1 ] ---> qf [ (1, N) ]
Rule# 99 : q809 [ b ] ---> q809 [ (b, L) ]
%%============================================
%%======== Machine Definition : BEGIN ========
%%======= Computing a Fibonacci number =======
%%============== Turing Machine ==============
%%============================================
C++ Simulator of a Turing Machine
* http://sourceforge.net/projects/turing-machine
* http://alexvn.freeservers.com/s1/turing.html
has been used to compute several Fibonacci numbers.
Raw Logs :
* http://groups.google.com/groups?th=1e653c4ef60faa44
|-|erc
Herc
Alex Vinokur
"|-|erc" <ferr...@hotmail.com> wrote in message news:4rOPa.596$7d2....@nnrp1.ozemail.com.au...
> Is there a graphic of the transition table?
>
> Herc
>
>
>
To compute Fibonacci numbers using the C++ Simulator of a Turing Machine
http://sourceforge.net/projects/turing-machine
one needs to prepare the following input :
* set of the states
* the alphabet
* the transition table (plain text, no graphic).
So, I didn't do a graphic of the transition table.
Regards,