Re: TM Tape is Always Finite

From: Arthur J. O'Dwyer (ajo_at_nospam.andrew.cmu.edu)
Date: 01/03/04 

Date: Fri, 2 Jan 2004 20:15:07 -0500 (EST)

On Thu, 1 Jan 2004, Russell Easterly wrote:
>
> "Acid Pooh" <poohonlsd@yahoo.com> wrote...
> > "Russell Easterly" <logiclab@comcast.net> wrote...
> > >
> > > Assume we give this machine a tape that has
> > > an infinite string of 0's. It would seem that
> > > TM1 will output an infinite string of 1's.
> >
> > No, you wouldn't have an output at all. This machine would never
> > halt.
>
> I don't know why everyone is so worried about a TM halting.

  Because that's the way you originally phrased the problem.
You referred to the idea that a TM could "output" a number, and
in traditional programming jargon, the only way you can see a
program's "output" is to wait for it to "halt," and then look at
what it's produced.

> The word "halt" does not appear in Turing's paper.

  I'm willing to bet that a majority of participants in this
discussion have not read Turing's paper in the last 20 or 30
years. I certainly have never read it. I get my knowledge
second-hand, from people who can explain ideas more clearly (one
hopes) than the original geniuses who came up with them. (Let's
hear it for Martin Gardner! :)
  But I am glad you posted a bit of the paper you're discussing,
because it is very important to figure out what we're talking
about, here, specifically.

> This is the definition of a computable number given by Turing:
>
> <quote>
> Computing machines.
> If an a-machine prints two kinds of symbols, of which the first kind (called
> figures) consists entirely of 0 and 1 (the others being called symbols of
> the second kind), then the machine will be called a computing machine. If
> the machine is supplied with a blank tape and set in motion, starting from
> the correct initial m-configuration,

  Please define "m-configuration," as defined in Turing's paper.

> 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.

  Okay. Here Turing is apparently assuming that the "sequence" printed
by the machine will have a beginning, though not necessarily an end.
It's not clear how he defines the beginning of the sequence, though --
is it left-to-right order? or chronological? Left-to-right has the
advantage of "intuitiveness," but chronological makes more sense
mathematically to me. Please clarify this point: briefly, what does
Turing mean by the word "prefacing"?

> 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.
>
> {233}
> 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.

  All right. This is fairly bizarre terminology, IMHO -- do you have
any idea why Turing chose these particular words to describe the two
kinds of machines? Perhaps a quote from section 8 would be in order.

> 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.
>
> We shall avoid confusion by speaking more often of computable sequences than
> of computable numbers.
> </quote>
>
> According to this definition, any TM that halts is circular and does NOT
> produce a computable sequence.

  Correct. Now that we know our definitions, or at least some of
them, we can conclusively say that for instance your TM1 "computes"
the sequence 11111..., which implies that all numbers differing from
the natural number 1 by an integer amount are "computable."

> I don't know if Turing allows symbols of the first kind to be overwritten.

  Nor do I. As you're the one with the paper, I suggest you try
to settle this question.

> In my proof, let "1" be the only symbol of the first kind and
> substitute "blank" for "0".
>
> TM1 as I define it is circle free and produces the computable sequence:
> .11111... (base 2)

  Incorrect. The computable sequence is 11111..., an infinite sequence
of 1's. The real number corresponding to that sequence is .11111...
(base 2), or the real number 1.

> > > Instructions for TM2:
> > >
> > > 1) Scan right until a 0 is found
> > > 2) Scan right until a second 0 is found
> > > 3) Backup and write a 1 on the previous 0
> > > Repeat

> Using Turing's definition, TM2 produces a computable sequence

  I doubt it. This depends heavily on the definition of the word
"prefacing" in Turing's paper.

> that represents the largest rational number less than 1.

  Blatantly false. No such number exists, computable or otherwise.
That's like saying that your machine computes the number of digits
in pi, or a recipe for granite cheesecake.

> .111...1110 (base 2)

  This is not correct notation. It reminds me very strongly of
Phil's ramblings, and I really do suggest you take a look at
Google Groups for sci.math, and search on "rational numbers
countable", "largest integer", and terms of that nature.

> This is essentially the same reason Turing gives why
> the diagonal argument doesn't work with computable numbers.
> The problem can be converted into determining whether
> every TM is "circular" or not.
> Turing proves this is impossible

  While it is certainly impossible to determine whether Turing
Machine X is circular, for some value of X, it doesn't necessarily
follow that the computable numbers are uncountable. For that,
you'd need to actually give a reference to Turing's proof, so
that we could look at it and see whether it proves what you think
it does.
  It may very well prove what you think it does. Before you
posted this quote, I think most participants assumed you were
talking about a different sort of "computable number" altogether,
one which I won't rehash here since it's irrelevant now.

> TM2 is not an arbitrary TM. It is easily specified.
> If we can not determine if TM2 is circle free,
> how can we say that any TM is circle free?

  The question of whether TM2 is circle-free depends entirely on
Turing's definition of "m-configuration." The question of whether
TM2 computes a number depends entirely on Turing's definitions of
"sequence" and of "prefacing."

> > I'm not sure why you think this is particularly important. By
> > construction, at any given time-step, a Turing machine has modified
> > only finitely many cells, but there is no upper bound on the number of
> > cells a Turing machine can modify. (There is a glaringly obvious
> > analogy with the natural numbers here).
>
> I am showing there is an upper bound.
> A TM can't write infinitely many unique representations.
> A TM can not compute an irrational number if it can only write finitely many
> cells.

  TM1 writes on infinitely many cells. A Turing machine can certainly
compute the following irrational number, though I have not bothered
to write out its state transitions:

  .10110111011110111110111111011111110111111110111111111011111111110...

  That number, which is approximately 0.71673, is computable, but
certainly not rational! Also computable: pi and e, among many
others.

-Arthur

Relevant Pages

  • Re: The Indescribable Random Numbers
    ... exists that generates the sequence f. ... numbers must be uncountably infinite. ... Cantor's diagonalisation process is not an algorithm in the sense most ... I agree that computing pi to n decimal places is unbounded as n ...
    (sci.math)
  • Re: TM Tape is Always Finite
    ... That is not how Turing defined them. ... then the machine will be called a computing machine. ... >> by it which are of the first kind will be called the sequence computed ... "symbols of the first kind" on every other square. ...
    (comp.theory)
  • Re: The Indescribable Random Numbers
    ... exists that generates the sequence f. ... numbers must be uncountably infinite. ... Cantor's diagonalisation process is not an algorithm in the sense most ... I agree that computing pi to n decimal places is unbounded as n ...
    (sci.math)
  • Re: Why does Cantor a target for cranks?
    ... instead we talk about the abstract rationals which are ... after which we cite an infinite sequence of zero digits) and others ... is in the sub-sequence that generates computable reals or not. ... computing algorithm that enumerates the integers, ...
    (sci.math)
  • Re: Church-Turing compared to Zuse-Fredkin thesis (two new papers)
    ... Circular and circle-free machines. ... If a computing machine never writes down more than a finite number of ... We shall avoid confusion by speaking more often of computable sequences than ... A static representation means that some finite portion of the tape ...
    (comp.theory)