Re: No Set Contains Every Computable Natural

From: Jim Nastos (nastos_at_cs.ualberta.ca)
Date: 02/18/04 

Date: Tue, 17 Feb 2004 16:42:15 -0700

M.C. wrote:
> > You can't input an infinite string to the tape. If you could, it wouldn't
> > be a Turing machine.

R.E. wrote:
> Requiring the input tape to be finite is a severe limitation.
> For example, no language, L, could contain every binary
> representation of rational numbers between 0 and 1.
> 1/3 has an infinite binary representation in base 2.

  Languages are usually defined as finite concatenations of a set of
alphabet symbols. For example, the set of natural numbers expressed in
unary notation is a perfectly fine language... a mistake you made in an
earlier post was to assume that a word "infinitely long" is in that
language; instead, this is an infinite language containing all 1-strings
of finite length.
  For your example above, there are better ways of representing every
rational between 0 and 1.

R.E. wrote:
> Every definition of TM's that I have seen assumes
> that an infinite tape of blanks is allowed.

  But the input (non-blank symbols) is always bounded in length by some
finite amount.

M.C:
> > No natural number requires an infinite unary representation. All may be
> > represented using a finite number of 1s.

R.E:
> There is no TM that can decide if the string has an
> infinite string of 1's.

  Russell, I don't see how your response is relevant to what Michael said.
His point is that the language {1^n | n is a natural number} is a set of
finite-lengthed strings. It is not hard to show that there is a TM that
can decide this language.
  And, yes, if you include an infinitely-long string of 1s, then no TM can
decide it (in a finite amount of time, which is a crucial requirement.)
This is why infinitely-long strings are not usually considered in
languages.

M.C:
> > All Turing machines can be finitely represented. There is no such
> > thing as a TM transition function that requires an infinite state
> > automata for representation.

R.E:
> There is no TM that can decide if the transition table is
> infinitely long.

  Again, your response is kind of irrelevant. His point is that if you
have a set representing the transition function, it MUST be finite sized
if it is going to represent a TM.

> > > The Halting Problem is ill posed.
> > > There is no set that contains every TM
> >
> > Sure there is : A = {<M> | M is a valid TM representation}
>
> It is impossible to decide if M is a valid representation.

  Actually, it is quite simple to decide if M is a valid representation.

> > It is easy to check, given a data structure, whether the input is a
> > valid TM or not.
>
> It is impossible for a TM to decide if M is a valid representation.

  Again, it is quite simple. Look up a definite of a Turing machine... it
is some tuple of sets, and it is straightforward to check that, for
example, the claimed "start state" is an element of the "state set." And
that the transitions form a subset of the cross product of the "state set"
with itself... and so on.

> > All natural numbers are computable. However, they _all_ can't be
> > generated in a single run of any algorithm/TM.
>
> The output of a TM can't contain a representation of every natural?

  That is correct. Since a TM must halt to complete its output, it can
only have a finite number of natural number representations.
  Don't feel that TMs are 'weak' because they can't output ALL the
naturals. What TM can do, however, is output all the natural numbers from
1 to k for arbitrarily large k.

> I didn't say that a TM can't print out certain natural numbers.
> I said that a TM that requires a fixed, finite amount of time to
> perform an operation can't print certain natural numbers in a
> reasonable amount of time.

  Taking about "withing a reasonable amount of time" has very little to do
with decidable sets or recursively enumerable ones. These sets do not say
anything about the time required to accomplish any computation; they are
merely telling you what can and can not be computed.
  You probably want to investigate the notion of time-bounded (or even
space-bounded) turing machines.

J

Relevant Pages

  • Re: Integers are really fractions?
    ... carry off the top of this infinite string of zeros, ... Giga2's representation. ... representations of the naturals you claim are also in there. ...
    (sci.math)
  • Re: Uncountability of the Rationals?
    ... of Pofnats (normal, mathematical, plain-old-finite naturals). ... What my proof about N+ indicates is not that its Bigulosity, tav, is ... either finite or infinite, but that it cannot be either, and therefore ...
    (sci.math)
  • Re: Galileos Paradox and the Project of the Reals
    ... the positive integers which I defined the other day. ... A finite real, then, may be defined as any finite natural, or any number between any two finite naturals on the real line, by subdivion of the unit interval. ... We can also construct a linear enumeration of the reals using powers as I suggested with the H-riffic numbers. ...
    (sci.math)
  • Re: Calculus XOR Probability
    ... If a quantitative set is mapped in ascending order from the naturals, with each increment in the domain, the range increases by some amount. ... Like it's the number of unit intervals, and the number of reals in the unit interval. ... You are using a form of infinite induction, making a claim for an infinite set based on all finite initial segments of it. ... don't have a definition for an arbitrary set of its "standard ordering" ...
    (sci.math)
  • Re: Uncountability of the Rationals?
    ... absolute size and those that do not. ... infinite sets, especially the standard N, starting at 0. ... you would be so kind) say which axioms you reject. ... since it contains all of the countable naturals. ...
    (sci.math)