Re: Turing Machines and Physical Computation

examachine_at_gmail.com
Date: 12/09/04 

Date: 9 Dec 2004 13:02:26 -0800

Stephen, you never cease to amaze me.

In this post, you do demonstrate that you know unbounded means
potentially infinite.

Therefore, at no point in execution, a TM can generate Pi. That is, it
computes Pi *only* in the limit, it *never* actually computes Pi, it
computes only finite prefixes of Pi.

Will you agree with the above, given what you say in your post?

Pi is still called a computable real, for the fact that nothing
*further* than finite prefixes can ever be computed. Maybe computable
in this sense is a figure of speech, a slight abuse of terminology, but
it serves to illustrate the difference between computable and
uncomputable reals. What the finite program for computing Pi in the
limit gives us is a *description*, not Pi itself. We never have Pi in
R. We only have approximations to it, even *in theory*. What writes on
the tape is what we have as you agree above: a finite string. [There is
an easy way to correct this of course, but let's not go into that
area.]

That is precisely what happens with a physical computer, until of
course they hit physical limits, which anything must abide by!

But earlier you said that a TM can compute Pi because it has an
*infinite tape*. I can find several posts where you said exactly that,
without ever mentioning that this infinity is potential and never
actual infinity. In particular, I told you that the tape is not
infinite: the infinite part is comprised entirely of blank symbols.

On other occasions, you assert that a TM does not have to abide by
physical limits because it is an idealization. I concede that. However,
I still think that this does not detriment from the physical reality of
TM model! What matters is that, there is no small enough TM derivation
that cannot be realized. Not that there are TM derivations that do not
fit into the space-time of our universe. As I mentioned before, I think
this does not matter, because no machine that big can ever fit into our
universe! Not just TMs!

Let alone the fact that a computer the size of the universe cannot be
called a personal computer.

I now tend to give credence to the possibility that our entire
disagreement was a definitional one (is the concept of "unbounded" a
different thing in an infinite universe, etc.?), although I suspected
that it was due to idealism. It is easy to detect which. Do you think
that TMs that are too large to fit in space-time exist in the sense of
the existence of a table or chair? Or do you, like me, think that the
TM is just another model of computation, such as cellular automata or
Lambda Calculus?

Consequently, do you agree with me in saying that computability and
computability in the limit are different concepts?

I think Russian mathematicians understood what "limit" meant long
before we started arguing about it in 2001, Stephen. We should perhaps
heed the words of the Russian school a littlle. We wasted so many posts
collectively.

Cheers, 

--
Eray Ozkural

Relevant Pages

  • Re: Can any old earther refute common genetic ancestry?
    ... variability to infinite variability. ... We live in a slightly bio-friendly universe. ...
    (talk.origins)
  • Re: Logarithm of transfinite numbers
    ... Tony Orlow wrote: ... But since you criticize other mathematics on ... widespread usage of the Leibniz notation, how in the limit via infinite ... The universe is infinite, infinite sets are equivalent. ...
    (sci.math)
  • Re: ping Frez
    ... physicists have had a particularly difficult relationship with the notion of boundlessness. ... The general theory of relativity predicts that singularities in which physical properties become infinite occur in the centre of black holes and in the Big Bang that kicked our Universe into existence. ... Unless we are missing something of fundamental importance, these observations indicate that our expanding Universe is about 14 billion years old, contains copious quantities of dark matter in some unidentified form, and is expanding at an accelerating rate. ...
    (alt.sports.football.pro.ne-patriots)
  • Re: Logarithm of transfinite numbers
    ... Tony Orlow wrote: ... But since you criticize other mathematics on ... widespread usage of the Leibniz notation, how in the limit via infinite ... The universe is infinite, infinite sets are equivalent. ...
    (sci.math)
  • Re: Well Ordering the Reals
    ... >>>Separation is sufficient to contradict the existence of such a set. ... >> There is no set in ZF which is the universe in a model (i.e. for any set ... Thus, with a non hereditarily finite set, ... So, if infinite sets are irregular, and finite sets are not, then, ...
    (sci.math)