Re: Complex Specified Information - Pitman Formula

On 2007-07-26, R. Baldwin <res0k7yx@xxxxxxxxxxxxxxxxxxxx> wrote:
"Seanpit" <seanpit@xxxxxxxxx> wrote in message
news:1185381379.407217.251680@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
On Jul 25, 9:01 am, Mark VandeWettering <wetter...@xxxxxxxxx> wrote:
[snip]
Pi isn't "all computable". Since it is an endless, never repeating
sequence,
we can never compute it all.

That's not the definition of a non-computable number.

"He [Alan Turing] defined a computable number as a real number whose
decimal expansion could be produced by a Turing machine starting with
a blank tape. He was able to demonstrate that the irational number pi
was computable."

http://www.amt.canberra.edu.au/turingb.html

I'm sorry, but a Turing machine can't compute pi, it computes
approximations
to pi. By definition, anything which is computable is computable by a
Turing machine _that halts_. Since the decimal expansion of pi is
infinite
and non-repeating, it is by definition uncomputable.

You are countering Alan Turing himself on this one. Do you have any
reference to back your own notion of computability up on this one? I
doubt it. Pardon the double negative, but the fact is that pi is not
uncomputable.

"What does "uncomputable" mean? Something is uncomputable if it
can't be represented in terms of a finite-sized computer program. For
instance, the number Pi=3.1415926235.... is *not* uncomputable. Even
though it goes on forever, and never repeats itself, there is a simple
computer program that will generate it. True, this computer program
can never generate *all* of Pi, because to do so it would have to run
on literally *forever* - it can only generate each new digit at a
finite speed. But still, there is a program with the property that,
*if* you let it run forever, then it *would* generate all of Pi, and
because of this the number Pi is not considered uncomputable. What's
fascinating about Pi is that even though it goes on forever and
doesn't repeat itself, in a sense it only contains a finite amount of
information -- because it can be compactly represented by the computer
program that generates it."

http://www.goertzel.org/benzine/QuantumComputingArticle.htm

You need to look up the definition of computability. Your definition
doesn't seem to be correct. But, I'd be very interested if you could
in fact find a reference that supports your definition. Good
luck . . .


I have to side with Sean on this one. In Turing's usage, pi falls under the
definition of a computable number. Turing explicitly states this in
paragraph 2 of his classic paper, "On Computable Numbers, with an
Application to the Entscheidungsproblem."

"In sections 9, 10 I give some arguments with the intention of showing that
the computable numbers include all numbers which could naturally be regarded
as computable. 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."
http://www.abelard.org/turpap2/tp2-ie.asp

Turing's definition of computable number is a bit farther down, but I find
its language a bit awkward. The Wikipedia article has a more directly stated
definition:

"In mathematics, theoretical computer science and mathematical logic, the
computable numbers, also known as the recursive numbers or the computable
reals, are the real numbers that can be computed to within any desired
precision by a finite, terminating algortihm."
http://en.wikipedia.org/wiki/Computable_number

I will cede the point, and apologize for the criticism. While I find
the terminology rather odd, I understand why it arises: Turing was trying
to demonstrate that the digits of pi are in fact computable, while the
vast majority of real numbers are not so computable. That is either a
profound or a simple result, depending upon your perspective.

Mark

.

Relevant Pages

  • Re: Cantors Diagonal Argument
    ... Because for any mapping of N to the interval [0,1) I can ... As far as I can tell, the number of states in the Turing machine ... > without AC we can only generate computable Reals which ...
    (sci.logic)
  • Re: An Alternate Model for the Reals
    ... If a Real Number can be associated with a Turing Machine it ... The set of ALL A-computable numbers is NOT A-complete. ... THE KLEENE HIERARCHY ... the constructible reals are a model for ACA_0; ...
    (sci.math)
  • Re: The Cantorists have fallen silent
    ... Can a Turing machine have no output? ... Suppose one is using a "doubly infinite" tape, ... mapping from tapes to reals such that every tape is a real. ...
    (sci.logic)
  • Re: The nature of uncomputability
    ... complexity, and how some sets of numbers are uncomputable (e.g. the ... there is an algorithm (a Turing machine) to compute ... Most reals are not ...
    (sci.logic)
  • Re: Computable functions/reals.
    ... has been more or less definite, standard, agreed, incontestable. ... and also to a standard idea of computable reals. ... if there exists a Turing machine which writes ... given a decimal expansion of x on the input. ...
    (sci.logic)