Re: Lambda Calculus and Turing Equivalence

From: Stephen Harris (cyberguard1048-usenet_at_yahoo.com)
Date: 12/02/04 

Date: Thu, 02 Dec 2004 16:07:30 GMT

<gds@best.cut.here.com> wrote in message
news:Bqyrd.28629$NC6.6974@newsread1.mlpsca01.us.to.verio.net...
> At 1 Dec 2004 12:04:41 -0800, examachine@gmail.com (Eray Ozkural exa)
> wrote:
>>torbenm@diku.dk (Torben Ęgidius Mogensen) wrote in message
>>news:<7zsm6qvyqk.fsf@pc-032.diku.dk>...
>>> A TM does not have an _infinite_ tape, it has an _unbounded tape_.
>>> This means that the tape is guaranteed to be as large as you need it
>>> or, equivalently, that the tape will grow as you need it but always
>>> stay finite.
>>>
>>> It isn't hard to write a TM simulator in pure lambda calculus. The
>>> converse is harder, but possible.
>>
>>Precisely my point.
>>
>>I am saying to those who say that PCs are not TMs, like Chapman and
>>Harris, that they do not know the difference between unbounded
>>(potentially infinite) and actually infinite. (Although they claim
>>that they do) The latter is a set theoretical notion that is not
>>required to depict TMs, I doubt this distinction was so clear back
>>then.
>

The difference between a TM and a PC is that the potential finite
memory of a TM exceeds the potential finite memory of a PC.

A TM is a hypothetical (theoretical) logical device that can in
principle compute problems that require greater storage than
some physical computer (PC) even if that PC had or could use
all the physical memory available in the physical universe and
execute to the end of time or heat death of the universe (no power).
A TM is also not constrained by a physical energy source to move the tape.

That is because the tape that Turing posited has no physical constraints.
Therefore a TM can compute more digits (a finite number) of Pi than any
PC (also finite) which is limited by memory and the heat death of the
universe. Pi or the square root of a prime number are still computable.
There is no claim that a non-computable number is being computed by
a TM than a PC cannot compute, but that a TM can compute a larger
amount (more digits each requiring more memory to hold them) of
finite digits of a computable number.

> Part of the problem is that there is a fair amount of literature that
> describes TMs as having infinite memory, e.g. the second paragraph of
> http://en.wikipedia.org/wiki/Turing_machine. (Arguably, this is an
> informal description.)
>
> I haven't read all of the articles in this and related threads, but so
> far none that I have seen have commented on the difficulty TMs have in
> modeling "ongoing computation," such as what is found in operating
> systems. (The Wikipedia article mentioned above has a short
> discussion of this.)
>
> --gregbo
> gds at best dot com

PCs and TM both compute computable functions. I don't see how
having an OS or a timing signal or any other ways that TMs and PCs differ
has any bearing on this thread. I think what is relevant from the Wiki url:

 http://en.wikipedia.org/wiki/Turing_machine
"Comparison with real machines"
"Turing machines would actually only be equivalent to a real machine that is
magically given an infinite amount of storage space."

Turing endowed his TM with a magical amount of storage potential
because physically, the amount of storage is not possible. A physical PC can
just not match the amount of information that can be held on Turing's tape,
even though the information storage required is finite in both cases. It is
like
the difference between a gallon of milk and a truckload of milk (or more).

It doesn't matter if you change "infinite" to unbounded. The TM described
by Turing in his 1936 has an unlimited, (as needed) tape. A physical
computer (PC) must always be (upper) limited. The amount of physical memory
that you can add to a physical computer will always eventually run
out at some huge point of required physical storage. Just because a number
is
finite does not mean it can be physically computed within a universe with
finite
resources. The TM is not governed a finite resource of memory because
it is not physical. Because a PC uses some ideas in the abstract
construction
of a Turing machine does not make a PC and TM equivalent. They both
compute computable functions, but the finite size of the computable numbers
is not identical. There is of course a huge overlap between computations
that can in principle be computed by a TM and those that can be computed
by a PC which has never been disputed.