6 expanded posts ยท every known parent and child
Hi all, Just a thought, Seems to me that a Turing Machine can't simulate a continous section of R for a simple reason, computers can only work on rational numbers and a continous section would have irrationals in it. Take care.
On Tue, 26 Jul 1994, Jim choate wrote: > Seems to me that a Turing Machine can't simulate a continous section of > R for a simple reason, computers can only work on rational numbers and > a continous section would have irrationals in it. Ok, I am kicking myself for saying this, but it is not the data on the tape, it is the information of the machene itself. It is at most a cardinal infinity, and even if there are irrational numbers there can't be a continum of these. It has more to do with there being "steps" than what the steps are. In a continum machene, you would not have steps or states. It is not clear if the quantization of time could do anything to this(like make it bogus). The quantization of spacial objects certainly makes a limit forbiding continum tapes. <warning, sci fi follows, don't even start to criticize this, it is too easy!> I was thinking you could get a quantum computer with an continum of states if you did not bind them, which could lead to : AP nwes: Today sientists at mega labs detonated a quantum computer with the intent of solving the recorded history of light recieved here on the earth at that instant back to the distribution of mater at approximatly 10-15 seconds after the big bang. This complements nicely the forward computation done by a similar explosion of smaller magtude. How is that for a wacky idea?
Marvin Minsky's old automata theory text (something like "Finite and Infinite Machines") has an intro to the computable reals (or constructable reals? can't remember) which the interested might like to read.
Andrew Purshottam says:
> Marvin Minsky's old automata theory text
> (something like "Finite and Infinite Machines")
> has an intro to the computable reals (or constructable reals?
> can't remember) which the interested might like to read.
I'll point out that the countability of the reals (or, rather,
uncountability) is a simple concept -- I've explained it in five
minutes to a twelve year old, so I see no reason why it can't be
quickly explained here. (I haven't paid much attention -- perhaps
someone else has done this already but I haven't noticed it.)
An infinite set is said to be countable if it can be mapped one to one
to the integers. (Actually, to the cardinals, or positive integers, in
most definitions, but it doesn't matter as I'll show in a moment). As
an example, I can map the even positive numbers to the positive
numbers very easily -- use the "divide by two" operator, and I can
map every even positive number to a positive integer, and vice versa.
All integers may be mapped to the positive integers in an equally
simple manner -- start by numbering 0 as 1, 1 as 2, -1 as 3, 2 as 4,
-2 as 5, 3 as 6, and in general all positive n go to 2n and all
negative n go to -2n+1.
It would seem that the rational numbers couldn't be counted, but in
fact they can -- you just have to be clever. Build a table like so
(I've only partially filled it in :-) and think of the row index as the
numerator and the column index as the denominator -- you will swiftly
see that you can number every fraction. (Actually, you overnumber them
in the sense that some numbers get more than one index this way --
fixing this is left as an exercise to the reader...)
1 2 3 4 5 6 7 8 ....
1 1 3 6 10 15 21 28 36
2 2 5 9 14 20 27 35
3 4 8 13 19 26 34
4 7 12 18 25 33
5 11 17 24 32
6 16 23 31
7 22 30
8 29
...
Now, you might think some clever trick could be used to map the reals
into the integers. Unfortunately, you cannot do it. I can prove that
quite easily, by contradiction.
For simplicity, lets just try to map the reals between zero and one to
the integers, and lets consider them expressed as binary numbers.
Imagine that I had built a mapping between this subset of the reals
and the positive integers. Any such mapping implies a list, that is,
that I could build a table like
1 .1010101101010010010010010101001.....
2 .0100001010100010100101001001010010...
3. .11000101001010110100010100010101001....
etc.
I can now construct a number that is not in the table. Take the first
binary digit from the first number in the table, and complement it. That
is the first digit in my constructed number. Take the second digit
from the second number and complement it -- that is the second digit
of the constructed number. Add in the complement of the third digit of
the third, the fourth digit of the fourth, etc. The number I have just
constructed can't be the first number in the imaginary table because
the first digit didn't match. It can't be the second because the
second didn't match. It can't be the third because the third doesn't
match. Indeed, it can't be any of them. Thus, you can't map the reals
to the integers.
The reals are thus in some sense a "bigger" infinite set than the
integers.
PerryPretty Good Privacy 2.6ui - Public-key encryption for the masses. (c) 1990-1993 Philip Zimmermann, Phil's Pretty Good Software. 27 May 94 Date: 1994/07/28 03:23 GMT You need a pass phrase to unlock your RSA secret key. Key for user ID "Dietrich J. Kappe <kap1@tao.cpe.uchicago.edu>" Enter pass phrase:
-----BEGIN PGP SIGNED MESSAGE----- Perry E. Metzger writes: [Countability proofs deleted...] For simplicity, lets just try to map the reals between zero and one to the integers, and lets consider them expressed as binary numbers. Imagine that I had built a mapping between this subset of the reals and the positive integers. Any such mapping implies a list, that is, that I could build a table like 1 .1010101101010010010010010101001..... 2 .0100001010100010100101001001010010... 3. .11000101001010110100010100010101001.... etc. I can now construct a number that is not in the table. Take the first binary digit from the first number in the table, and complement it. That is the first digit in my constructed number. Take the second digit from the second number and complement it -- that is the second digit of the constructed number. Add in the complement of the third digit of the third, the fourth digit of the fourth, etc. The number I have just constructed can't be the first number in the imaginary table because the first digit didn't match. It can't be the second because the second didn't match. It can't be the third because the third doesn't match. Indeed, it can't be any of them. Thus, you can't map the reals to the integers. The reals are thus in some sense a "bigger" infinite set than the integers. Small but important correction: the number that you contructed may in fact be a binary equivalent to one already in the list. Example: .0111111... .1000000... Claim: For a given real x, there exist at most a finite number of equivalent binary representations. (In fact, just 2.) Proof: Left as an excercise. I think everyone can see how to splice this little lemma into the proof. Of course, the proof isn't nearly as clean as before, so it may take more than 5 minutes for a 12 year old (or 12 minutes for a 5 year old :-). Dietrich Kappe kap1@wimpy.cpe.uchicago.edu - - -finger for PGP public key- -----BEGIN PGP SIGNATURE----- Version: 2.6 iQCVAwUBLjck/zdLyfjamMpJAQHt8AP+LmFAQK2KpjcxrEq8jhW2eUM/qNqVVHsu j53E0TTwfWGB1ih7KttCY/0GrwpeW1DGGdhp6iLTjCwqW/bE52voY/PdmlqTc/PB yjwhC9Tw/Mb+gKUleh45JW5f8szhAxv6tGYCLLitdJ3TQHNkJM520RhuJGskPJxB DUkqzPcL4Yk= =a2fn -----END PGP SIGNATURE-----