The Ten Turing Machines Real Number Counting Proof
From: HERC777 (herc777_at_hotmail.com)
Date: 10/28/04
- Next message: Karl-Olav Nyberg: "Re: Infinity is not that big!"
- Previous message: HERC777: "Cantor's complete list assumption is not extrapolated"
- Messages sorted by: [ date ] [ thread ]
Date: 28 Oct 2004 16:20:44 -0700
Not everyone follows what I mean when I use
UTM(n, 0) neN
as the countable real list. UTM is any one of a special set of
Turing Machines that can emulate *any* other Turing Machine.
A Turing Machine is essentially a computer program in the format
of a binary finite state machine augmented with an infinite memory
tape.
The smallest UTM is a large program several thousand states
in size, it is very clumsy and slow. It has to read 2 numbers off
the tape so it has to decode a ternary input constructed out of
binary pairs of digits and also emulate a table of numbered states
with its primitive binary operations. The input, working memory and
the data structure of states (the program it's emulating) all have to
be adjacent on the single infinite tape. Its not a practical device,
no RAM.
But there are small UTMs, using different machines to TMs yet
they are equivalent in the algorithms they can emulate.
The EVAL function in LISP (a functional language) is essentially
a UTM. EVAL("print" + " 10") => 10. Functional languages were only
theoretical until a student of John McCarthy suggested handcoding
the eval function and the rest of LISP would run. Miranda uses
a smaller subset of lambda calculus again, a set of about 10
'supercombinator' functions that can emulate any other function.
S a b c = a c (b c)
K x y = x
These 2 functions are equal in power to a Turing Machine.
S K K x
= K x (K x)
= x
I (the identity function) is also used but is not necessary
since SKK = I here.
There are other models of computation, the high order function
TWICE() that applies its function-argument to itself is thought
of as the number 1. TWICE(TWICE()) is the number 2. Constructions
of this one function yield addition and multiplication functions,
in theory some function of the form TWICE(TWICE((TWICE)TWICE(TWICE)))
is a UTM. Neural nets are Turing equivalent, recursive functions,
there are several classes and types of computation, numerous
computer languages, sometimes completely different in how they
operate, and numerous ways to program a UTM on each, yet they are all
equivalent in WHAT THEY COMPUTE.
Given this, it should be easy to find 10 different UTMs.
Each UTM is input one natural number at a time, from 1 onwards
it emulates the 1st computer program and outputs the result,
emulates the 2nd computer program and outputs the result.
UTM1( 1, 0 ) = 7
UTM1( 2, 0 ) = 555555555555
UTM1( 3, 0 ) = ?
UTM1( 4, 0 ) = 1111..
Now I'll briefly address the doorman arguments.
1/ We place a "0." at the start of the number and focus the
demonstration
on reals between 0 and 1.
2/ We can also use digit places instead of 0 as the program argument,
so the
program terminates for each digit. A cartestion counting method
like ones
use for counting rationals can be used for multitasking infinite
numbers with
infinite digits.
3/ UTM1(3, 0) hasn't terminated yet, will it ever? Scheduling the
processes
in a multi tasking format this is of little concern. The point is
whether the
set of all emulated programs can compute every real. We're not
going to
achieve a standard bijection, not-halted-yet can be considered an
11th digit
for the purposes of diagonalisation, and these digits may update to
a fixed
digit after more processsing. The 11th digit work around is not a
weakness of
using programs to generate numbers, it is a contraint of the
diagonalisation technique.
Now we run the 10 Universal Turing Machines.
UTM1
1 0.0494873739
2 0.000004343939
3 ?
4 0.99999999999
5 0.5000000000000
UTM2
1 0.5000000000
2 0.00000000000
3 0.99999999999
4 0.101010101010
...
UTM10
1 0.0000000000
2 0.1111111111
3 0.1111111111
4 0.9999999999
Instead of 1 anti-diag number, we have 10.
The diagonals of each UTM :
UTM1 diagonal 0.0059
UTM2 diagonal 0.5090
UTM3 diagonal 0.3746
UTM4 diagonal 0.2234
UTM5 diagonal 0.1223
UTM6 diagonal 0.6563
UTM7 diagonal 0.3483
UTM8 diagonal 0.5403
UTM9 diagonal 0.2355
UTM10 diagonal 0.0119
Assume each UTM is independant of one another.
The 1st digit of the diagonal has several different numbers from each
of
the 10 UTMs.
1st digit of the diagonals {0,5,3,2,1,6,3,5,2,0}
2nd digit of the diagonals {0,0,7,2,2,5,4,4,3,1}
3rd digit of the diagonals {5,9,4,3,2,6,8,9,5,1}
Each UTM list of reals has an anti-diag number, but does
this number appear on another UTM list?
For an anti-diag number to be unique, its 1st digit cannot
be any of {0,5,3,2,1,6,3,5,2,0}, that leaves 4, 7, 8, 9.
The 2nd digit cannot be in {0,0,7,2,2,5,4,4,3,1}, that leaves 6, 8, 9.
The 3rd digit of anti-diag cannot be in {5,9,4,3,2,6,8,9,5,1}.
All digits are taken here, so there is no ant-diag number.
Frequently along the diagonal, all 10 digits will occur across
the 10 UTM lists. Any supposed number not on the lists could
occur at these positions.
So diagonalisation only finds new numbers from a single list,
or from a small set of lists less than the number of digits.
>From a set of 10 lists there is no technique that will find
a new number to all of the lists.
There are 2 possibilites, each list stands as a complete set of real
numbers, or the 10 lists combined are 'complete'.
If the 10 lists have a union to count all numbers then
we can construct a single list enumerating all the numbers.
UTM1 real1
UTM2 real1
UTM3 real1
..
UTM10 real1
UTM1 real2
UTM2 real2
..
This list is amenible to diagonalisation and a new real could be
constructed.
CONTRADICTION
Therefore, each list of UTMk can be a complete set of reals, and by
the Church Turing Thesis each list is exactly the same set of reals.
Herc
- Next message: Karl-Olav Nyberg: "Re: Infinity is not that big!"
- Previous message: HERC777: "Cantor's complete list assumption is not extrapolated"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
