Re: Church-Turing compared to Zuse-Fredkin thesis (two new papers)

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

Date: Sun, 15 Feb 2004 04:18:47 GMT

"Russell Easterly" <logiclab@comcast.net> wrote in message
news:R--dndv_wuIXILPdRVn-uA@comcast.com...
>
> "Stephen Harris" <stephen.p.harris@sbcglobal.net> wrote in message
> news:O1xXb.12743$B53.5007@newssvr29.news.prodigy.com...
> >
> > "Russell Easterly" <logiclab@comcast.net> wrote in message
> > news:if6dnWHskv8BmbPdRVn-uw@comcast.com...
>
> > You are talking about an infinite process utilizing finite steps.
> > The definition employs a finite process utilizing finite steps.
> > An algorithm does not permit specifying an infinite number
> > of steps/symbols as part of the input. That violates its definition.
> >
> > "First, Turing required three finite­ness conditions:
> > (F1) the number of symbols;
> > (F2) the number of squares observed at any one moment;
> > (F3) the number of states.
> >
>
> Notice that the definition above does not say the process must end
> after a finite number of steps. My objection was to:
>
Yes, it does.

How do you explain (F3)? The number of states must be finite
so how can you have a finite number of states and an infinite
number of steps? Turing discusses the operation of the Turing
machine in the 1936 paper. I will quote this below, Turing writes:

"I shall also suppose that the number of symbols which may be
printed is finite."

SH: A finite number of steps is required to print a finite number of
symbols (digits in the expansion of Pi) not an infinite number of steps.

> 2.. M will, if carried out without error, produce the desired result in a
> finite number of steps;
>
> Turing did not require that a TM halt after a finite number of steps
> in his 1936 paper "On Computable Numbers with an application to the
> Entscheidungsproblem". In this paper, Turing defines a computable
> number as:
>
> Circular and circle-free machines.
>

I am going to snip this because you are not quoting from the
portion of Turing's 1936 paper which applies to the issue at hand.

http://www.abelard.org/turpap2/turpap2.htm

"Computing is normally done by writing certain symbols on paper. We may
suppose this paper is divided into squares like a child's arithmetic book.
In elementary arithmetic the two-dimensional character of the paper is
sometimes used. But such a use is always avoidable, and I think that it will
be agreed that the two-dimensional character of paper is no essential of
computation. I assume then that the computation is carried out on
one-dimensional paper, i.e. on a tape divided into squares. *I shall also
suppose that the number of symbols which may be printed is finite.*"

SH: When something is bounded, then it is not infinite: More Turing:
"The behaviour of the computer at any moment is determined by the symbols
which he is observing. and his "state of mind" at that moment. We may
suppose that there is a *bound B to the number of symbols or squares which
the computer can observe at one moment. If he wishes to observe more, he
must use successive observations.

"We will also suppose that the number of states of mind which need be taken
into account is finite."

The reasons for this are of the same character as those which restrict the
number of symbols. If we admitted an infinity of states of mind, some of
them will be "arbitrarily close" and will be confused. Again, the
restriction is not one which seriously affects computation, since the use of
more complicated states of mind can be avoided by writing more symbols on
the tape."

SH: > > (F3) the number of states. (the third finiteness condition)
is finite --> 'The states of mind are restricted to finite and an infinity
of states of mind is not admitted.'

Turing uses the word moves rather than steps of the computation:

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

Equivalence between machine moves/steps and states of mind of the
human computor. Turing writes:
"We may compare a man in the process of computing a real number to a machine
which is only capable of a finite number of conditions q1, q2, ..., qR which
will be called "m-configurations".

"The operation actually performed is determined, as has been suggested on
p.250, by the state of mind of the computer and the observed symbols. In
particular, they determine the state of mind of the computer after the
operation is carried out."

"We may now construct a machine to do the work of this computer. To each
state of mind of the computer corresponds an "m-configuration" of
the machine." [SH: Turing uses computer for a human computor.]
" The move which is done, and the succeeding configuration, are
determined by the scanned symbol and the m-configuration."

"The "computable" numbers may be described briefly as the real numbers whose
expressions as a decimal are calculable by finite means."

"In particular, I show that certain large classes of numbers are computable.
They include, for instance, the real parts of all algebraic numbers, the
real parts of the zeros of the Bessel functions, the numbers Pi, e, etc. The
computable numbers do not, however, include all definable numbers, and
an example is given of a definable number which is not computable."

Regards,
Stephen

Relevant Pages

  • Re: Church-Turing compared to Zuse-Fredkin thesis (two new papers)
    ... Turing discusses the operation of the Turing ... > "We will also suppose that the number of states of mind which need be ... a finite number of squares on the tape. ... The halting problem is also a red herring. ...
    (comp.theory)
  • Re: What is the Result from Invoking this Halt Function?
    ... His Turing machines are *intended* to keep running ... infinite string it was constructed to compute. ... It could halt after only writing a finite number of bits. ...
    (sci.logic)
  • Re: Steps beyond "Hello World" program
    ... you can write a C program that examines the memory trace left by ... Turing complete is defined as being able to compute ... mathematical Intuitionism denies the reality or possibility of this ... > A system that has an infinite pile of RAM sitting next to it that just ...
    (comp.programming)
  • Re: A case for HTML as a programming language
    ... but a Turing machine without an infinite tape is not a Turing ...
    (comp.programming)
  • Re: Steps beyond "Hello World" program
    ... you can write a C program that examines the memory trace left by ... > it merely says that you can do any calculation in that language (i.e. ... > the definition of Turing complete means that you have infinite memory, ...
    (comp.programming)