Re: Turing Machines and Physical Computation
From: Stephen Harris (cyberguard1048-usenet_at_yahoo.com)
Date: 11/22/04
- Next message: Lester Zick: "Re: Turing Machines and Physical Computation"
- Previous message: David Longley: "Re: Turing Machines and Physical Computation"
- In reply to: John Savard: "Re: Turing Machines and Physical Computation"
- Next in thread: Eray Ozkural exa: "Re: Turing Machines and Physical Computation"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Mon, 22 Nov 2004 00:23:54 GMT
"John Savard" <jsavard@excxn.aNOSPAMb.cdn.invalid> wrote in message
news:41a0f0ff.2213961@news.ecn.ab.ca...
> On 21 Nov 2004 09:05:19 -0800, examachine@gmail.com (Eray Ozkural exa)
> wrote, in part:
>
>>You are missing the entire point that computation is meant to be a
>>physical process. That is all there is to computation. It is a theory
>>of computing machines. And it describes a large number of them. Let's
>>get down to your particular objections to my detailed analysis.
>
SH: Eray, his is another one of your premises that conflicts with the facts.
Turing was mathematician interested in the foundations of mathematics.
Hilbert made up a list of 23 questions to put mathematics on firm footing.
I'm pretty sure that it is number 10 on this list that Turing referred to in
his famous 1936 paper,
"On computable numbers, with an application to the Entscheidungsproblem"
The paper had two purposes to define the nature of an algorithm and
to give a better negative answer to Hilbert's challenge:
"A decision problem was a general question: "Given any sequence of symbols,
is it a formula?" or "Given any formula, is it provable?" A solution to a
decision problem was an effective procedure, a uniform method or algorithm,
specified by a finite set of rules, by which each instance of the general
question could be answered in a finite number of steps. An effective
procedure could not appeal to intuition, understanding, creativity, or
guesswork, and always generated the correct answer.
http://www.artsci.wustl.edu/~gpiccini/Alan%20Turing%20and%20the%20Mathematical%20Objection.pdf
L. E. J. Brouwer was the main supporter of intuitionism, according to which
an existence proof for a _mathematical object_ was admissible only if it
exhibited a construction of the object (Brouwer 1974)."
Brouwer was also against Cantorian set theory which also made use
of the diagonalization process. Turing was improving Godel's result
which answered Hilbert question 10 negatively. Turing was attempting
to show his answer as a constructive process for exhibiting proof of a
***mathematical object***, not the "physical object" you claim.
eray wrote:
>>You are missing the entire point that computation is meant to be a
>>physical process. That is all there is to computation.
You have how this happened jumbled. Compters, when Turing wrote
this article, were office clerks equipped with pencil, paper and eraser.
Maybe they had an old fashioned hand-driven adding machine that you
see in old movies. Computation was done by office clerks. Turing claimed
that his Turing machine could perform mechanical procedures like these
clerks; that it was mechanical in the sense of by rote, no ingenuity was
involved, no creativity. That was the computation performed by human
computer and claimed for turing machines.
When Turing wrote this (1936) , there wasn't any technology of digital
computers existing in order to point the purpose of direction you claim,
realization of a physical computing machine. I think he was exposed to
a primitive analog computer in 1937. After he worked on encryption
during WWII I think he got the notion of a physical device. Then someone
realized that tubes could be used to compute with and I think the first
proto-digital computer was around 1946. I think it was 1948 when Turing
introduced thinking machines---much after his Turing machine paper.
You just seem to be ignoring the fact that the theory that present day
computers borrow heavily from started as a theory. It was a
mathematical-logical theory not at all intended to provide a blueprint
for physical digital computers. That happened afterward, a development.
That is why I can find so many quotes on the web describing a turing
machine as an abstract hypothetical device. That is its historical origin.
http://www.unidex.com/turing/tm_intro.htm
"A Turing machine can be thought of as a primitive, abstract computer. Alan
Turing, who was a British mathematician and cryptographer, invented the
Turing machine as a tool for studying the computability of mathematical
functions. Turing's hypothesis (also known has Church's thesis) is a widely
held belief that a function is computable if and only if it can be computed
by a Turing machine. This implies that Turing machines can solve any problem
that a modern computer program can solve. There are problems that can not be
solved by a Turing machine (e.g., the halting problem); thus, these problems
can not be solved by a modern computer program."
I'm not arguing with this. I factually stated some problems are tractable
for TMs that are not tractable for PCs because of time. The heat death
of the universe comes about because of the passage of time which means
there is no more energy available in order to power physical computing.
This is somewhat like the idea that quantum computers are supposed to
solve some computable problems that are intractable for conventional PCs.
I say somewhat because this introduces time, which is not a TM factor.
How many intractable problems are there? Infinite.
>>But every couple of months, a naive mathematician will show up (not
>>you) and try to purport an imaginery dichotomy between physical
>>computation and Turing computation. That is unfortunate, very
>>unfortunate indeed, because in my opinion it shows a systematic mental
>>error.
>
You are committing a systematic mental error. The one you refer to is
when people mistakenly claim that TMs cannot compute what a digital
computer (pc) can compute. This is true without claiming inherent
randomness in the physical computer. I have stated the converse of this
statement. That some problems are intractable for PCs because of the
time element; but those problems are not intractable for TMs because
Turing invented TMs without any reference to time and he gave the
TM an infinite tape so there is no shortage of memory problem (the
tape doesn't halt unexpectedly because it runs out like an adding machine)
which eliminates physical constraints from TMs that do impact PCs.
I made no assertion that the topic of physical computation was historically
less important now. The physical aspect was certainly less developed, if at
all, when the mathematical theory of a TM was created. TMs are not physical.
> Although a theory of physical computing machines is possible, we do not
> have such a theory as yet.
>
> The Turing Machine, as A. M. Turing specified it, cannot calculate "pi",
> but it can calculate any finite number of digits of pi, such as
> (10^(10^(10^(10^(10^1000))))) digits of pi, even though no
> physically-realizable computer could calculate that many digits of pi.
>
> Turing _did_ specify the Turing machine that way, so it is a fact that
> he made the same "systematic mental error" you refer to. Why did he do
> such a thing?
>
> Because it made it possible for him to derive results from his theory in
> a reasonable amount of time. Determining what the limits of computation
> in the physical universe are, and what can be done within those limits,
> is a very complicated problem. Assuming infinite memory capacity is a
> simplifying assumption that makes for a theory much easier to derive and
> work with.
>
> What is the use of such a theory, a theory that doesn't refer to the
> real world? If certain things cannot be done with even an infinite
> memory, then they cannot be done with a finite memory. And many things
> that can be computed don't need an infinite amount of memory, or even an
> absurdly large finite one. So the Turing machine is an *approximation*
> to a real computing machine.
>
> From the points and lines of Euclidean geometry, as compared to the
> lines made with real pencils and the pinpricks made by the point of a
> real compass, mathematicians have always approximated the real world by
> abstractions which are not physically realizable. This makes the
> symbolic manipulations in mathematics simpler - and thus makes them
> realizable instead of impractical. Giving this up would mean giving up
> mathematics, because taking into account the limitations of the real
> world in every case would make many fields far too complicated to
> investigate.
>
> John Savard
> http://home.ecn.ab.ca/~jsavard/index.html
I think the literature supports your statements:
http://plato.stanford.edu/entries/turing-machine/
"In modern terms, the tape serves as the memory of the machine, while the
read-write head is the memory bus through which data is accessed (and
updated) by the machine. There are two important things to notice about the
definition.
The first is that the machine's tape is infinite in length, corresponding to
an assumption that the memory of the machine is infinite. The second is
similar in nature, but not explicit in the definition of the machine, namely
that a function will be Turing-computable if there exists a set of
instructions that will result in the machine computing the function
regardless
of the amount of time it takes. One can think of this as assuming the
availability of infinite time to complete the computation.
[SH: I prefer to think of it as having no time involved, rather than
infinite.]
These two assumptions are intended to ensure that the definition of
computation that results is not too narrow. This is, it ensures that no
computable function will fail to be Turing-computable solely because there
is insufficient time or memory to complete the computation. If a function is
not Turing-computable it is because Turing machines lack the computational
machinery to carry it out, not because of a lack of spatio-temporal
resources."
--------------------------------------------------------------------
"These are called abacus computers by Lambek (Lambek 1961), and are known to
be equivalent to Turing machines.
The modern digital computer is subject to finiteness constraints that we
have abstracted away in the definition of abacus machines, just as we did
in the case of Turing machines. Physical computers are limited in the number
of memory locations that they have, and in the storage capacity of each of
those locations, while abacus machines are not subject to those constraints.
Thus some abacus-computable functions will not be computable by any physical
machine. (We won't consider whether Turing machines and modern digital
computers remain equivalent when both are given external inputs, since that
would require us to change the definition of a Turing machine.)"
-----------------------------------------------------------------------------
"Commercially available computers are hard-wired to perform primitive
operations considerably more sophisticated than those of a Turing machine
--add, multiply, decrement, store-at-address, branch, and so forth. The
precise constitution of the list of primitives varies from manufacturer to
manufacturer. It is a remarkable fact that none of these computers can outdo
a Turing machine. Despite the Turing machine's austere simplicity, it is
capable of computing anything that any computer on the market can compute.
Indeed, since it is an abstract or notional machine, a Turing machine can
compute more than any physical computer. This is because
(1) the physical computer has access to only a bounded amount of memory, and
(2) the physical computer's speed of operation is limited by various
real-world constraints.
It is sometimes said, incorrectly, that a Turing machine is necessarily
slow, since the head is continually shuffling backwards and forwards,
one square at a time, along a tape of unbounded length. But since a
Turing machine is an idealised device, it has no real-world constraints
on its speed of operation."
Regards,
Stephen
- Next message: Lester Zick: "Re: Turing Machines and Physical Computation"
- Previous message: David Longley: "Re: Turing Machines and Physical Computation"
- In reply to: John Savard: "Re: Turing Machines and Physical Computation"
- Next in thread: Eray Ozkural exa: "Re: Turing Machines and Physical Computation"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
