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

From: Russell Easterly (logiclab_at_comcast.net)
Date: 02/17/04 

Date: Tue, 17 Feb 2004 01:33:00 -0800

"Stephen Harris" <stephen.p.harris@sbcglobal.net> wrote in message
news:LhXXb.13180$gP1.7891@newssvr29.news.prodigy.com...
>
>
> Dave Seaman:
> A set is recursive if there is an effective procedure (a Turing machine,
> perhaps) that can decide membership in the set. That is, the machine
> halts and returns 1 if the input is in the set, and the TM halts and
> returns 0 if the input is not in the set.

This is the definition of a decidable language at wikipedia:
http://en.wikipedia.org/wiki/Decidable_language

A decidable or recursive language is a formal language that is a recursive
set, i.e., for which there exists an algorithm to solve the following
decision problem: Given string w, does w belong to the language? The
algorithm is not allowed to run into an infinite loop and has to produce a
YES/NO answer for any input string after a finite amount of time. To
formalize the rather vague term "algorithm", one usually employs Turing
machines, but several other equivalent approaches are possible.

This definition should say "finite number of steps" instead of "finite
amount of time"
I will come back to this.

This is the definition of a recursively enumerable language:
http://en.wikipedia.org/wiki/Recursively_enumerable_language

Definition 1. Given string w as input, the algorithm halts and outputs YES
if and only if w belongs to the language L. If w does not belong to the
language L, the algorithm either runs forever, or halts and outputs NO.

There is a second definition that you might want to read.

Let me define a language, L, that consists of all unary representations of
natural numbers.
1 = one, 11 = two, 111 = three, etc.

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.

The set of all natural numbers is not a recursive set.

Consider what happens when we talk about the set of all TM's.
Assume we can encode the state transition table of a TM using
a natural number. This set can not be recursive for the same
reason that the natural numbers are not recursive. Given a
string, i, we can not be sure that TM(i) is actually a TM
because we can not be sure that i is actually a natural number.

No set can contain every computable natural number.

Proof:
Assume a TM produces a tape with all of the natural numbers
encoded in unary where each natural is followed by a 0 (or a blank).
Turing gives the state transition table of such a TM
 010110111011110...

I can define a three state TM that will find a natural number
that is not on this tape:

1) Read right until there is a 0.
2) Read right until a second 0 is found.
3) Backup and write a 1 on the previous 0.
Repeat steps (1) through (3).

This TM will always produce a tape that has exactly one 0.
This 0 will be at a finite position on the tape and the string of 1's
that preceds this 0 represents a natural number that was not on
the original input tape.

The Halting Problem is ill posed.
There is no set that contains every TM just as there is no set
that contains every computable natural number.

Now, about the difference between "finite amount of time" vs
"finite number of steps". There are theories of computing where
a TM can perform an infinite number of steps in finite time.
These are called "hypercomputers".
http://en.wikipedia.org/wiki/Hypercomputer

A non-deterministic Turing machine is an example of a hypercomputer.
Another example is an "accelerated Turing Machine". An ATM performs
the first operation in one unit of time, the second operation is 1/2 unit
of time, the third operation in 1/4 unit of time, etc. An ATM will perform
an infinite number of operations after two units of time.

Assume we have a computer that can perform an operation in one
nanosecond. The language, L, that I defined above is not even
recognizable if we expect an answer before the universe freezes over.
We can easily compute a natural number, n, that is so large that
our nanosecond computer will take 15 billion years to recognize
n as a natural number. There is only a finite number of naturals
less than or equal to n. There is an infinite number of naturals
larger than n. Nearly all natural numbers are larger than n.

So, we see that we have to assume that a TM can perform
an infinite number of operations in finite time to even say
that L is recursively enumerable.

Russell
- Zeno was right. Motion is impossible.

Relevant Pages

  • Re: No Set Contains Every Computable Natural (was Church-Turing compared to Zuse-Fredkin thesis)
    ... > A decidable or recursive language is a formal language that is a recursive ... > YES/NO answer for any input string after a finite amount of time. ... Consider what happens if x is an infinite ... There is only a finite number of naturals ...
    (comp.theory)
  • Re: Why does Cantor a target for cranks?
    ... Does To distinguish the between the size of the set of naturals and the size of a set of representations of the naturals, such as the binaries or the decimals? ... I distinguish them with different measure, one related to density on the real line, and the other related to combinatorial size as string length grows. ... Subsets of the reals are sets of points within the line. ... For a fixed alphabet and finite but unbounded word lengths, the set of words in a language and the set of naturals biject naturally. ...
    (sci.math)
  • Re: No Set Contains Every Computable Natural
    ... > unary notation is a perfectly fine language... ... You still need a human to decide if a representation is "finite". ... The input tape would be a string of blanks followed by a 0. ... > naturals. ...
    (comp.theory)
  • Re: Internet, Goldbach conjecture, cranks and anticranks.
    ... inconsistent" in the language of arithmetic is to assign to formulas natural numbers as their codes, and show that the basic syntactic properties can be expressed as arithmetical predicates of the codes of the objects these properties apply to. ...
    (sci.math)
  • Re: Could there be such a FOL theory?
    ... Our ordinary picture of the natural numbers is only partially captured in Peano arithmetic, and indeed can only be partially captured by means of the language of arithmetic even if we disregard all questions of axiomatization, due essentially to the open-ended nature of the induction principle, which we take to apply to any property we might recognize as meaningful and determinate. ... the concept of induction chain be preserved, ... I think I now understand your question better, and it is not obvious how to represent a sequence of the kind you envision without separately introducing the "ordinary" naturals to serve as "place markers". ... If we introduce a new unary function symbol S' we can take S', S', S', ... ...
    (sci.logic)