Re: TM Tape is Always Finite

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


Date: Sat, 3 Jan 2004 14:54:30 -0500 (EST)


On Sat, 3 Jan 2004, Russell Easterly wrote:
>
> "Arthur J. O'Dwyer" <ajo@nospam.andrew.cmu.edu> wrote...
> > On Thu, 1 Jan 2004, Russell Easterly wrote:
<snip>
> > > <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.
>
> I think he means what is now called the state transition table.
> The TM's instructions.

  According to Turing's paper, to which you have kindly provided a
link, an "m-configuration" is what we today would call a "state."
http://www.abelard.org/turpap2/tp2-ie.asp#section-1
It's not the whole transition table; it's merely one of the states
listed in that table (which may or may not be said to "contain" the
rest of the table; that's a philosophical point that's not relevant
here). For example, "State 1" is an m-configuration. "State 2"
is a different m-configuration.
  The machine, Turing says, will start in the "correct initial
m-configuration," which is just his way of saying that it has a
defined starting state.

> > 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"?
>
> Turing assumes that all TMs start in a defined initial state at the
> beginning (leftmost) position of a blank tape.

  Okay; this makes the most sense, so I'll accept it. Unfortunately
for us, Turing simply does not say in his paper what "shape" the tape
is supposed to be. In other words, he defines the symbols on the
tape, S(r), in terms of their positions r; but he never defines the
range of r. Is r an integer, a positive integer, an integer in the
range [0, 1024), or something else entirely?
  From here on, I'll assume that r is a positive integer. This is
*not* what I'd originally been thinking -- I had been assuming that
r was an integer (positive or negative), and thus that the tape was
"two-way infinite" instead of only "one-way infinite." If you don't
see the difference, or don't understand what those phrases are meant
to mean, just skip it for now. From here on, r is a positive integer.

> I think Turing assumes the output tape will be read from left to right.
> Later in the paper, Turing adopts the convention of only writing
> "symbols of the first kind" on every other square.
> He often writes other symbols (of the second kind?) between
> the 0s and 1's. He states that these other symbols are removed
> at some point, but isn't very specific about when or how this happens.

  I think you are correct. Symbols of the first kind may not be
overwritten, although symbols of the second kind may be overwritten.
The tape is read from left to right, and only symbols of the first
kind matter as far as the computed sequence is concerned.

> "Prefacing" means putting a decimal point in front of a binary string.
> Turing is trying to show that a TM can generate any real number.

  Yes. Now that I realize that r is constrained to be positive,
this makes sense -- there is always a "left side" of the tape at
which we can insert a decimal point (at r=0, so to speak).

> > > 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.
>
> I have no idea why Turing defines computable numbers this way.

  I was actually referring to the terms "circular" and "circle-free"
to describe machines that we today would see were exactly isomorphic
to [but not identical to] the terms "halting" and "non-halting." What
does the idea of "circle" have to do with the finitude of symbols
printed by a machine? [Rhetorical -- unless you really have some
etymology here, don't bother answering that. Just a clarification
of what I meant.]

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

  I'm sorry, I misread your machine. I read "right" and thought
"left." Obviously, TM2 is exactly equivalent in its output to TM1
(assuming that the tape starts out with all 0's on it, or doing as
you suggested and replacing the word '0' by the word 'blank').

> > > 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.
>
> This sequence may not represent a real number, but it is computable.

  All computable sequences, by definition, represent real numbers.
Any sequence of zeroes and ones, prefixed by a point, is the digital
representation of *some* real number.
  Unless the antecedent of "this sequence" is "granite cheesecake,"
in which case you're half right; granite cheesecake is not a real
number, but neither is it computable by Turing's method.

> > > .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.
>
> I don't know who "Phil" is, but I have started several
> threads about the largest natural number.

Google Groups "phil sci.math numbers"

> I don't know why you find the idea so bizarre.
> The idea that there is a finite number of natural numbers
> is certainly not as strange as the idea that there are
> more real numbers than natural numbers.

  Perhaps not -- but it's certainly not as correct!

> Several people have suggested that this proof says
> there is a finite number of natural numbers.
> This is incorrect.

  Right.

> This proof shows that no set
> can contain every natural number.

  Wrong. Consider the set usually written blackboard-bold /N/,
the set of natural numbers. It's the set {0,1,2,3,...}. It
contains all natural numbers. It can be constructed inductively
as the set S such that 0eS and xeS->(x+1)eS, where e represents
the is-an-element-of relation.

> This is not the same as saying there is a largest natnum.
>
> Just the opposite.
> A set can't contain every natnum precisely because
> there in no largest natmun.

  Luckily for the universe, there is no logical requirement that
every set must contain a largest element. Consider the set of
even numbers, or the set of real numbers less than 1, or the
set of Greek playwrights.

> > > 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 does not. I'm embarrassed that I did not see the reversal
earlier. Cantor's diagonal argument, applied to the real numbers,
proves that R is uncountable. Turing showed that the diagonal
argument could *not* be applied to the computable numbers, which
means that he did *not* prove that the set of computable numbers
was uncountable.

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

  TM2 is circle-free. It never stops printing 1's, which are
symbols of the first kind. Thus by definition it is circle-free.

> > TM1 writes on infinitely many cells.
>
> No it doesn't.
> At least, no one can prove that it does.

  I can. Inductively; in the same way that I can show that if
I give an idiot a card reading

  "Turn this card over."

on both sides, and the idiot obeys the orders on the card, he
will never stop turning the card. In the same way, the "orders"
you gave to TM1 tell it to keep printing '1' forever; thus, it
will never stop printing '1's.

> It is simple to show that the number of 1's
> written by TM1 is some multiple of the number
> of 1's written by TM2.
>
> How does one prove TM2 writes an infinite number of 1's?

  Inductively.

> >A Turing machine can certainly
> > compute the following irrational number, though I have not bothered
> > to write out its state transitions:
> >
> > .10110111011110111110111111011111110111111110111111111011111111110...
>
> This is the same sequence I use in "Cardinality of Computable Numbers".
> Turing gives a similar string as an example of the output of a TM.
> He provides a state table to produce the string 001011011101111...
>
> If you let TM2 read this tape it will produce a sequence, of 1's
> followed by a 0, that is longer than any such sequence on the initial tape.

  Incorrect. Besides, even if you did let TM2 start with this tape,
that wouldn't produce a computable sequence -- computable sequences
are made starting with a blank tape, according to Turing's paper.

> > That number, which is approximately 0.71673, is computable, but
> > certainly not rational! Also computable: pi and e, among many
> > others.
>
> These numbers are computable only if you can show there is
> a "circle free" TM that computes the relevant infinite sequence.
> I doubt any TM can be shown to be "circle free" as Turing defines it.

  You just said that Turing had given a state table for a TM that
computed 0.71673...! Obviously that number is computable by a TM,
then -- it's computable by the TM that Turing just finished defining!

  Read the responses to Phil's ramblings before proceeding along
this line of inquiry -- you're getting in way over your head in
very shallow water.

-Arthur