444 views

Skip to first unread message

Jun 21, 2003, 12:38:39 PM6/21/03

to

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

==========================================

Jun 21, 2003, 5:39:47 PM6/21/03

to

In article <bd21po$oagok$1...@ID-79865.news.dfncis.de>, "Alex Vinokur"

<ale...@connect.to> wrote:

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

Jun 21, 2003, 8:34:54 PM6/21/03

to

Alex Vinokur wrote:

> Is there any program of computing Fibonacci numbers on a Turing Machine?

> 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

Jun 22, 2003, 8:44:47 PM6/22/03

to

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.

Jun 22, 2003, 8:47:26 PM6/22/03

to

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

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

Jun 22, 2003, 9:16:19 PM6/22/03

to

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.

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

Jun 23, 2003, 1:55:04 AM6/23/03

to

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:

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.

Jun 23, 2003, 9:20:56 AM6/23/03

to

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

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

Jun 23, 2003, 10:47:09 AM6/23/03

to

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.

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

Jun 23, 2003, 12:04:06 PM6/23/03

to

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.

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?

Jun 23, 2003, 12:13:19 PM6/23/03

to

"Mark A. Biggar" wrote:

>

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

>

> 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

Jun 23, 2003, 2:20:06 PM6/23/03

to

In article <474b22da.03062...@posting.google.com>,

cris...@hevanet.com (Daniel.) wrote:

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.

Jun 23, 2003, 3:45:22 PM6/23/03

to

Hans Aberg 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.

>

> 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

Jun 23, 2003, 7:00:51 PM6/23/03

to

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

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

Jun 24, 2003, 5:13:23 AM6/24/03

to

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

Jun 24, 2003, 10:01:31 PM6/24/03

to

hab...@matematik.su.se (Hans Aberg) wrote:

> cris...@hevanet.com (Daniel.) wrote:

>> hab...@matematik.su.se (Hans Aberg) wrote:

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

Jun 25, 2003, 3:49:39 AM6/25/03

to

(cleared-up bits have been trimmed throughout)

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

Jun 25, 2003, 4:04:35 AM6/25/03

to

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

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

Jun 25, 2003, 10:24:24 AM6/25/03

to

In article <a3eaa964.03062...@posting.google.com>,

xant...@well.com (Kent Paul Dolan) wrote:

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.

Jun 25, 2003, 2:51:41 PM6/25/03

to

hab...@matematik.su.se (Hans Aberg) wrote (more times than this, but

these are the most clearly expressed ones):

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.

Jun 26, 2003, 4:44:36 AM6/26/03

to

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

Jun 26, 2003, 5:51:50 AM6/26/03

to

"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

=====================================

Jun 27, 2003, 10:07:28 AM6/27/03

to

On Mon, 23 Jun 2003 13:20:56 +0000, tcho 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.

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

Jun 27, 2003, 11:19:18 AM6/27/03

to

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.

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.

Jun 27, 2003, 11:35:54 AM6/27/03

to

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.

Jun 27, 2003, 12:18:40 PM6/27/03

to

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.

Jun 27, 2003, 1:18:38 PM6/27/03

to

In article <A7_Ka.35450$XG4.24460@rwcrnsc53>,

>Torkel Franzen wrote:

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

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

Jun 27, 2003, 2:16:36 PM6/27/03

to

In article <3efc7c6e$0$3945$b45e...@senator-bedfellow.mit.edu>,

tc...@lsa.umich.edu wrote:

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.

Jun 27, 2003, 2:16:48 PM6/27/03

to

In article <A7_Ka.35450$XG4.24460@rwcrnsc53>, "Mark A. Biggar"

<ma...@biggar.org> wrote:

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

Jun 28, 2003, 4:41:02 PM6/28/03

to

In comp.theory tc...@lsa.umich.edu wrote:

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

> 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

Jun 29, 2003, 5:42:41 PM6/29/03

to

In article <3efdfd5e$0$49110$e4fe...@news.xs4all.nl>,

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

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.")

Jul 6, 2003, 12:22:07 PM7/6/03

to

"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

==========================================

Jul 8, 2003, 8:18:27 AM7/8/03

to

"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

=====================================

Jul 8, 2003, 11:56:25 PM7/8/03

to

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

>

> ==========================================

> Alex Vinokur

> mailto:ale...@connect.to

> http://www.simtel.net/pub/oth/19088.html

> http://sourceforge.net/users/alexvn

> ==========================================

> 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

Jul 9, 2003, 12:49:15 AM7/9/03

to

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

Jul 12, 2003, 3:00:24 AM7/12/03

to

Is there a graphic of the transition table?

Herc

Jul 12, 2003, 10:05:29 AM7/12/03

to

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

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu