Re: Church-Turing compared to Zuse-Fredkin thesis (two new papers)

From: Stephen Harris (stephen.p.harris_at_sbcglobal.net)
Date: 02/16/04 

Date: Mon, 16 Feb 2004 00:28:03 GMT

Hello Russell,

Actually, I think this portion of post contains some interesting points.
I enjoyed thinking more about the consequences of Turing, 1936.

"Russell Easterly" <logiclab@comcast.net> wrote in message
news:R--dndv_wuIXILPdRVn-uA@comcast.com...
>
> "Stephen Harris" <stephen.p.harris@sbcglobal.net> wrote in message
> news:O1xXb.12743$B53.5007@newssvr29.news.prodigy.com...
> >
> > "Russell Easterly" <logiclab@comcast.net> wrote in message
> > news:if6dnWHskv8BmbPdRVn-uw@comcast.com...
>
> Turing did not require that a TM halt after a finite number of steps
> in his 1936 paper "On Computable Numbers with an application to the
> Entscheidungsproblem". In this paper, Turing defines a computable
> number as:
>

I thought more about what you might mean by this. Turing uses Pi as
an example of a computable number--his paper is an explanation of
his understanding of a computable number.

> Circle free means the TM never halts.

This appears to be reversed. Circular machines may experience this.
Turing: A sequence is said to be computable if it can be computed by a
circle-free machine. The "computable" numbers may be described briefly as
the real numbers whose expressions as a decimal are calculable by finite
means.

Definable:
Definition: x is definable iff there is a predicate P(t) such that t is the
only t such that P(t). Implicit is the notion that the definition is finite.
Definable is not the same as computable:

  Let x be the real number whose n-th digit is 0 iff the n-th Turing machine
stops and 1 otherwise. x is defined but not computable.
The Halting Problem says that no computer program or Turing machine can
determine if ALL computer programs or Turing machines will halt or not halt
on ALL inputs.

Circular and circle-free machines.
If a computing machine never writes down more than a finite number of
symbols of the first kind it will be called circular. Otherwise it is said
to be circle-free.

A machine will be circular if it reaches a configuration from which there is
no possible move, or if it goes on moving, and possibly printing symbols of
the second kind, but cannot print any more symbols of the first kind. The
significance of the term "circular" will be explained in §8.
Computable sequences and numbers.
A sequence is said to be computable if it can be computed by a circle-free
machine. A number is computable if it differs by an integer from the number
computed by a circle-free machine

> I realize that the definition of computable number has changed
> since Turing's first paper, but Turing's definition includes
> all irrational numbers.
>

Why do you think so? Pi and e are irrational and their computability
is a special property and Turing writes (1936):

"In §§ 9, 10 I give some arguments with the intention of showing that the
computable numbers include all numbers which could naturally be regarded as
computable. In particular, I show that certain large classes of numbers are
computable. They include, for instance, the real parts of all algebraic
numbers, the real parts of the zeros of the Bessel functions,
the numbers X, e, etc.

The computable numbers do not, however, include all definable numbers, and
an example is given of a definable number which is not computable.

It must be remembered that we have attached rather a special meaning to the
phrase "U defines I". The computable numbers do not include all (in the
ordinary sense) definable numbers. Let P be a sequence whose n-th figure is
1 or 0 according as n is or is not satisfactory. It is an immediate
consequence of the theorem of §8 that P is not computable. It is (so far as
we know at present) possible that any assigned number of figures of P can be
calculated, but not by a uniform process. When sufficiently many figures of
P have been calculated, an essentially new method is necessary in order to
obtain more figures.
8.
It may be thought that arguments which prove that the real numbers are not
enumerable[5] would also prove that the computable numbers and sequences
cannot be enumerable . It might, for instance, be thought that the limit of
a sequence of computable numbers must be computable. This is clearly only
true if the sequence of computable numbers is defined by some rule.

The fallacy in this argument lies in the assumption that J is computable. It
would be true if we could enumerate the computable sequences by finite
means, but the problem of enumerating computable sequences is equivalent to
the problem of finding out whether a given number is the D.N of a
circle-free machine, and we have no general process for doing this in a
finite number of steps. In fact, by applying the diagonal process argument
correctly, we can show that there cannot be any such general process."

A Higly Random Number
Veronica Becher, Sergio Daicz, and Gregory Chaitin
"In his celebrated 1936 paper Turing defined a machine to be
circular if it performs an infinite computation outputting only finitely
many symbols. We define #alpha as the probability that an arbitrary machine
be circular and we prove that #alpha is a random number
that goes beyond w-omega , the probability that a universal
self delimiting machine halts."

Although almost all (in the sense of measure theory) real numbers are
random, an effective example of one such number was by no means granted.
Chaitin's definition of randomness lead to a natural example [4]. Based on
his theory of program size, Chaitin formalized the notion of lack of
structure and unpredictability of a random sequence: the prefixes of a
random sequence
can not be algorithmically compressed. Any structure or regularity in a
sequence could be considered for compressing it, that is, for codifying
certain amount of bits of the sequence in a program having substantially
less bits. Thus, in Chaitin's theory a sequence is defined to be random if
its prefixes are as long as the computer programs needed to generate them.
Chaitin conceived a sequence with this property: the binary expansion of
w-omega. w-omega relates to the simple task Turing found that no computer
could do: solve the halting problem. w-omega is the probability that a
universal self delimiting machine will eventually halt.
w-omega is not computable because its first n bits would enable us to answer
Turing's halting problem for all programs up to n bits in size, and this is
impossible.
As there are countably many universal machines we can speak of the class of
the w-omega-numbers, the real numbers that are their halting probabilities.

> Another poster stated that PI is computable because there is a TM
> that will recognise any finite approximation of PI. For example, this
> TM will say that 3, 3.1, 3.14, ..., are all valid approximations of PI,
> but 4, 5.13, etc, are not.
>

Practically speaking :-) if an advanced civilization dropped off the
first hundred digits of Pi after the 2 trillion mark, we couldn't sort it
or compare it to an existing expansion of Pi since we are only up
to about 2 billion places of Pi. However, in theory, I think that some
TM can produce any hugely long expansion of Pi, any finite arbitrary
expansion of Pi. It does not of course compute the last digit of a
infinite number. Now if Pi were non-computable or limited then
there is no guarantee that it could print out any huge finite sequence
and do a comparison. Because Pi is computable, it does mean that
you can compare it to some fragment, no matter how finitely long but
not infinite, and see if the sequence under question is contained in
the hugely long output. But I don't think there is a way to tell how
long, or more correctly to how many places you must evaluate Pi
till the fragment becomes reproduced within the entire parent sequence.
You can also prove that Pi is within upper and lower boundaries
unlike the w-omega which I don't think has a lower converging path.

> Every real number can be defined as a Cauchy sequence or
> Dedekind cut. Using this definition, it is possible to create a TM
> that will recognise all finite approximation of any particular
> irrational.
>

This seems a bit odd to me. Not the real number part, but
"it is possible to create a TM that will recognise all finite
approximation of any particular irrational."

For instance, irrationals are infinitely long. Two different
irrational numbers can have the same sequence of say
up to 50,000,000 (zillion) places and then diverge. I think the
a 5,000 digit (or any) finite approximation of an infinite
irrational will fit an infinity of "particular irrationals". There is
also an infinity of finite approximations. Just like Pi is infinitely
long-->how many finite approximations of Pi are available
in that infinity? This is like the problem of identifying finite
"random" appearing sequences as truly random. Isolated,
you cannot tell if they are part of a larger generating rule.

This also reminds me of Chaitin and his definition of
randomness. Pi is not random according to his definition
because it can be generated by a shorter algorithm.
Chaitin says that only equal length input to produce
equal length output is random. No algorithmic compression
is allowed. There are truly 'random real numbers'. Meaning
they are *not* produced by an algorithm.

Well what algorithm can examine fragment sequences and
see if they are truly random? Pi passes all the randomness tests,
but is algorithmic, so tests are not the answer. I think it can be
established that there is a class of infinite, random numbers, but
now what method (or algorithm) to determine if a particular
sequence has been generated by some function like Pi
(indistinguishable from random) or is the true daughter of
randomness as perhaps recording atomic decay of a nucleus
expressed in values of time (is available for this inspection.
The decay has a random time structure. So this analogy is
why I don't think there is such a method as:
"it is possible to create a TM that will recognise all finite
approximation of any particular irrational."

> I think a better definition of "computable number" would be to
> say a number is computable if there exists a TM that produces
> a tape with a "static" representation of the number.
> A static representation means that some finite portion of the tape
> remains "static", or unchanged, even if the TM never halts.
>
> For example, if a TM write "3.14..." to the output tape, and we can can
> show that this TM will never come back and overwrite the first n
> positions of the tape, for any finite n, then we have a TM that
> computes PI.
>
>
> Russell
> - 2 many 2 count
>
> I think a better definition of "computable number" would be to
> say a number is computable if there exists a TM that produces
> a tape with a "static" representation of the number.
> A static representation means that some finite portion of the tape
> remains "static", or unchanged, even if the TM never halts.
>

SH: How is your idea an improvement over what Turing has already
done? I will quote a piece from his 1936 paper and then provide the
greater context below:

"The symbols on E-squares will be liable to erasure. The symbols on
F-squares form a continuous sequence. There are no blanks until the
end is reached."

Background:
"If the machine is supplied with a blank tape and set in motion, starting
from the correct initial m-configuration, the subsequence of the symbols
printed by it which are of the first kind will be called the sequence
computed by the machine. The real number whose expression as a binary
decimal is obtained by prefacing this sequence by a decimal point is called
the number computed by the machine.

At any stage of the motion of the machine, the number of the scanned square,
the complete sequence of all symbols on the tape, and the m-configuration
will be said to describe the complete configuration at that stage. The
changes of the machine and tape between successive complete configurations
will be called the moves of the machine.

The convention of writing the figures only on alternate squares is very
useful: I shall always make use of it. I shall call the one sequence of
alternate squares F-squares and the other sequence E-squares. The symbols on
E-squares will be liable to erasure. The symbols on F-squares form a
continuous sequence. There are no blanks until the end is reached. There is
no need to have more than one E-square between each pair of F-squares: an
apparent need of more E-squares can be satisfied by having a sufficiently
rich variety of symbols capable of being printed on E-squares. If a symbol
J- is on an F-square S and a symbol I is on the E-square next on the right
of S, then S and J will be said to be marked with I. The process of printing
this I will be called marking J (or S) with I."

SH: Recall that Turing's idea of machine computable is equivalent to
what a human being, using pencil, paper and eraser can calculate
using a mechanical/repetitive/by rote procedure. So suppose you
are using the by hand method of calculating the square root of 2
to 87 places. You will compute this one step at a time for each
digit which is a finite process. Why do you need a record of your
34th calculation, assuming you haven't made a human calculating error?
Why do you need more than your 86th calculation numeric value
with which you will perform the same algorithmic procedure once
again to evaluate the square root of 2 to one more place, the 87th?

When an TM algorithm for computing Pi is working, it is computing
Pi one digit at a time. The tape is considered to be of infinite length.
so it doesn't matter whether previous results are stored, really. But
why do you need anything more than your last previous result stored?
I ask this question because I'm trying to figure out why your suggestion
is an improvement over keeping the symbols stored in a continuous
sequence on the F-squares as mentioned above?

A summary:
http://www.computerintegration.com/Theory/AxiomaticBase/TuringsLaws/OnComputation.htm
"Expressions are computable if they contain numeric values that can be
expressed by a sequence of real finite numbers, such as decimal numbers, and
the number of steps in the calculation is also finite. Such numbers are
stored in the machine as finite integers and other numbers such as decimal
numbers and complex numbers are represented by multiple integers such as the
vectors. [So he is definitely taking about finite fields where 9 + 9 = 8
(radix 10.) Infinitely long numbers like e can, however, be calculated to a
finite precision. So he is definitely taking about convergent algorithms
(finite means.)] "

The machine, or more accurately its' program must be circle free. This means
it must not enter a situation where it either stops working, or continues
working without producing any results.

A circular machine might manifest itself by printing a subset of values from
a computation, or printing data labels with no values. Thus computation
requires that all sequences including loops have a finite length and all
choices to be made on the end-state of expressions that are computable.
Algorithms must also be convergent.

Regards,

Stephen

Relevant Pages

  • Re: Chex Wat: Pi is "random" and "not predictable"?
    ... their output sequence. ... The fact is that an algorithm can also be used to ... first was about the probability of finding an apparent match. ... They may be matched within e at an infinite ...
    (talk.origins)
  • Re: an true information theory
    ... > outputs, and figures out that the algorithm must be A1, there ... > there is an infinite number of stages n such that P's guess at ... > sequence of algorithms, strike off every algorithm that appears ... I've read that quantum computing may improve tractability but ...
    (sci.math)
  • Different Kinds of Infinity
    ... hypothesis that it is in fact the correct algorithm and that it has ... other substrings within the normal number that match that finite sequence. ... with each successful prediction. ... They may be matched within e at an infinite ...
    (talk.origins)
  • Re: best approach to generate random number in java
    ... Because if one has access to the algorithm, ... >> it to the same initial state, it will produce the same sequence. ... Well, infinite children, and infinite play. ... >> Then, if the quantum computer approach were to fail, strongly implying ...
    (comp.lang.java.programmer)
  • Re: Turing vs. Godel (Newbie Question) (A simple example)
    ... program) which doesn't halt, ... Turing shows that for any Turing machine M, M does not solve every instance of the halting problem. ... He does this by constructing a counterexample, but the counterexample depends on M. ... What Turing proves is the lack of any algorithmic pattern in the sequence of halting answers, not the impossibility of finding some particular term in the sequence. ...
    (sci.math)