Re: No Set Contains Every Computable Natural (was Church-Turing compared to Zuse-Fredkin thesis)

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

Date: Tue, 17 Feb 2004 16:04:17 GMT

"Michael N. Christoff" <mchristoff@sympatico.caREMOVETHIS> wrote in message
news:dzmYb.4044$d34.673767@news20.bellglobal.com...
>
> "Russell Easterly" <logiclab@comcast.net> wrote in message
> news:odydnXiTFf4ZQqzdRVn-ig@comcast.com...
> >
> > "Stephen Harris" <stephen.p.harris@sbcglobal.net> wrote in message
> > news:LhXXb.13180$gP1.7891@newssvr29.news.prodigy.com...
> > >
> > >
> > This is the definition of a recursively enumerable language:
> >
> > This language is recursively enumerable. Given a string, x, there exists
a
> > TM that
> > will halt after a finite number of steps if x is a member of L.
> > This language is NOT decidable. Consider what happens if x is an
>> infinite string of 1's. The TM will not halt after a finite number of
steps.
> >
>
> You can't input an infinite string to the tape. If you could, it wouldn't
> be a Turing machine.
>

No, but you can input finite instructions which generate infinite output.
Russell is right about Turing saying this, and I found it repeated:

A Highly Random Number by Becher, Daicz, and Chaitin:

"In this note we present a natural example of a random number
that goes beyond the class of omega-numbers. The idea goes
back to Turing's celebrated paper "On computable numbers,
with an application to the Entscheidungsproblem" [11],
where he describes the computable numbers as the real numbers
whose decimal expansion is calculable by finite means.
According to Turing's definition, a number is computable if
its decimal expansion can be written down by a circle free
machine. This is a machine that performs an unending
computation in the course of which it writes down infinitely
many symbols. Otherwise, if it writes down only finitely many,
Turing defines the machine to be circular. Circular machines
reach a configuration from which there is no possible move,
or go on moving, but do not print any more symbols."

SH: You might not want to call this an algorithm which has
a "terminating" clause, but it is a computable method. See 1) Finiteness

Knuth, Vol. 1, Sec. 1.1:

"The modern meaning for algorithm is quite similar to that of
_recipe_,_process_, _method_, _technique_, _procedure_, _routine_,
_rigmarole_, except that the word "algorithm" connotes something
just a little different. Besides merely being a finite set of
rules that gives a sequence of operations for solving a specific
type of problems, an algorithm has five important features:

  1) Finitness. An algorithm must always terminate after a finite
     number of steps. [...] (A procedure that has all of the
     characteristics of an algorithm except that it possibly lacks
     _finitness_ may be called a _computational method_. [...])

(A procedure which has all the characteristics of an algorithm
 except that it possibly lacks finitness may be called a
"computational method". Besides his algorithm for the greatest
common divisor of two integers, Euclid also gave a geometrical
 construction that is essentially equivalent to algorithm E,
 except that it is procedure for obtaining the ``greatest common
 measure'' of the lengths of two line segments; this is a
 computational method that does not terminate if the given
 lengths are ``incommensurate''). [SH: for intererested constructivists]

  2) Definitess. Each step of an algorithm must be precisely
     defined; the actions to be carried out must be rigorously and
     unambiguously specified for each case. [...]

  3) Input. An algorithm has zero or more _inputs_: quantities
     that are give to it initially before the algorithm begins, or
     dynamically as the algorithm runs. [...]

  4) Output. An algorithm has zero or more _outputs_: quantities
     that have a specified relation to the inputs. [...]

  5) Effectiveness: An algorithm is also generally expected to be
     _effective_, in the sense that its operations must all be
     sufficiently basic that they can in principle be done exactly
     and in a finite length of time by someone using pencil and
     paper. [...]

(A procedure which has all the characteristics of an algorithm
 except that it possibly lacks finitness may be called a
"computational method". Besides his algorithm for the greatest
common divisor of two integers, Euclid also gave a geometrical
 construction that is essentially equivalent to algorithm E,
 except that it is procedure for obtaining the ``greatest common
 measure'' of the lengths of two line segments; this is a
 computational method that does not terminate if the given
 lengths are ``incommensurate'')."

I think Church's (1937a) description agrees with "infinite symbols".

"The author [i.e. Turing] proposes as a criterion that an infinite
sequence of digits 0 and 1 be "computable" that it shall be
possible to devise a computing machine, occupying a finite space
and with working parts of finite size, which will write down the
sequence to any desired number of terms if allowed to run for a
sufficiently long time. As a matter of convenience, certain further
restrictions are imposed on the character of the machine, but these
are of such a nature as obviously to cause no loss of generality -
in particular, a human calculator, provided with pencil and paper
and explicit instructions, can be regarded as a kind of Turing machine."

The Broad Conception of Computation by Jack Copeland

"Is addition over the computable numbers a computable
function? (That is, is x+y computable whenever x and y
are both computable numbers?) The answer is 'yes', but
off the top of one's head one might think otherwise,
for if x (or y) is a computable number having an infinite
decimal representation, how can x be input, given Turing's
restriction that the input inscribed on the tape must
consist of a finite number of symbols?

The solution is to input x in the form of a program which,
if inscribed on the (otherwise blank) tape of some universal
Turing machine, would cause the machine to calculate the
decimal representation of x digit by digit. Nothing tricky
is going on here. The program inscribed on the tape is, after
all, a sequence of symbols, and this particular sequence of
symbols has no less a claim to be counted as a representation
of the number, x, than '14' and '1110' have to be counted as
representations of the number fourteen.

In short, Turing has given us a new method for representing
numbers; and in this system there are finite representations
of some of the numbers which, in the decimal system, can be
represented only by means of an infinite sequence of symbols.

To return to the machine that is to add x and y, where x and
y are any computable numbers: once the representations, in
Turing's ingenious system, of x and y have been inscribed on
the tape, the machine is set in motion. First it calculates
the first digit of the decimal representation of x and
remembers it; next it calculates the first digit of the
representation of y; then it adds these two digits, using a
left­to­right addition procedure; then it turns to the second
digits of the representations, and so on. Each digit of the
decimal representation of x+y is produced by the machine in
some finite number of steps.

I hope the discussion so far has afforded some insight into
what a computable number is, in Turing's restricted sense of
'computable number'. A number is computable, in his sense,
just in case the number can be expressed by means of a certain
finite string of symbols, namely a string of symbols which, if
inscribed on the otherwise blank tape of some universal Turing
machine, will cause the machine to churn out the decimal
representation of the number."

SH: I think this means that a TM can add Pi and "e" digit by digit.
I posted not to argue on Russell's side, but because I thought this
Turing ingenuity deserved some recognition. I think the terminating
requirement makes more sense when applied to a digital computer.
I think there is one term. "not halting", doing double duty for two
different reasons. Printing Pi can continue to output symbols, a
circle-free machine, but a circular machine, can continue to move
but doesn't output symbols. So it is no longer a 'generative' case.

BTW, Chaitin has a new, warm, e-book online about the history
and philosophy of developing primes, randomness and Omega.

http://www.cs.auckland.ac.nz/CDMTCS/chaitin/omega.html
META MATH! The Quest for Omega by Gregory Chaitin

Regards,
Stephen

Relevant Pages

  • Re: misconceptions on computer science
    ... >> Show me an algorithm that is beautiful but useless. ... You haven't given a single example that furthers your position. ... >> What specific thing that Turing did are you talking about? ... Because those sound like engineering projects to me. ...
    (comp.object)
  • Re: Powers and logic
    ... quasi wrote: ... It is easy to give an algorithm which could be calculated ... one can always find the leading digit by inspection. ... The space requirement would exceed the capacity of ...
    (sci.math)
  • Re: Large-numbers division way too slow -- what to do?
    ... > algorithm is now responsible for most of the slowness. ... I want to return the quotient or the remainder). ... In the division function, at the very bottom, I placed: ... processing the last digit becomes the remainder. ...
    (sci.crypt)
  • Re: continued fractions
    ... The "one bit at a time" algorithm is just a special case of the ... The dividend and divisor will be expressed as ... The crucial part here is the "guessing" of the digit. ... digit is 1, and the result of the subtraction is your new w; ...
    (comp.lang.forth)
  • Why are reals uncountable yet algorithms countable (long)?
    ... If you are going to say: construct a number from one digit ... you cannot enumerate the infinite digits.I have read that, unlike reals, ... one of these algorithms would also be an algorithm ... enumeration of algorithms cannot produce all reals? ...
    (sci.math)
Loading