News for hackers. Stuff that matters.
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by 0x0203 on Thursday June 17, 2021 @09:26AM (#27539315)
I know I'm pretty inept when it comes to this subject, but can someone help me understand how the first three points of Turing's philosophical justification listed above can be true? For example, in computing the sequence of n values of an infinite series or the first n digits of pi, how can the claim be made that this can be done in a finite amount of space or with a finite number of states?
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by mcguire on Thursday June 17, 2021 @02:39PM (#27542944)
Turing's machine includes an "infinite" tape. The number of states, the state transitions, and the number of symbols are finite, but an unbounded number of symbols can be written, one to a cell, on the tape.
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by chriswarbo on Thursday June 17, 2021 @10:43AM (#27540109)
We're allowed an unlimited amount of paper, but each piece has a finite size, and hence each piece is in one of only finitely-many distinguishable states. Turing called these piece-of-paper-states "symbols", and arranged the pieces of paper in a "tape" of unlimited length (a stack of sheets, or a library of books would also work; but moving between the pieces would be more complicated).

In fact, we only ever need 2 symbols, e.g. 0 and 1. This is because any set of symbols can be replaced by a set of numbers, and those numbers can be written in binary (with a fixed width, to avoid needing 'spacers'). This can require a lot more machine states, since those states allow the machine to 'remember' the bits it's read so far (e.g. if we're using 8 bits at a time, then we need enough states to "remember" what the first 7 bits were as we're reading the 8th).

For a calculation like pi, we can use the tape to (a) write down the digits (or bits) of pi, and (b) keep track of intermediate variables needed for the calculation. One simple approach to keeping track of intermediate variables is to store them in order on the tape, where each variable is a sequence of 1 symbols, separated by 0 symbols. For example a tape like: 111010010 represents four variables with values 3, 1, 0 and 1 (the number of 1s we see before we hit a 0). This actually corresponds to Peano arithmetic, if we use the symbols S and Z instead like SSSZSZZSZ.

An algorithm which spits out digits of pi forever (e.g. http://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/sp... ) could work by moving its 'variables' section further and further to the right, allowing the digits of pi to accumulate, e.g.

    Start
    
    ^

    Initialise variables and output/variables separator
    |VARIABLES

    Move variables to make space for next digit
    _|VARIABLES

    Calculate and write next digit
    3|VARIABLES

    Move variables to make space for next digit
    3_|VARIABLES

    Calculate and write next digit
    31|VARIABLES

    and so on
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by mensetmanusman on Thursday June 17, 2021 @10:18AM (#27539832)
It might be because pi isn’t infinite in practice. E.g. we could use all the available energy in the universe and only calculate up to a finite digit (ignoring the information storage issue!).

Whether the abstract infinite pi ‘exists’ is up for metaphysical debate :)

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by chriswarbo on Thursday June 17, 2021 @10:48AM (#27540150)
Here is pi, written as a number to infinite precision (from http://davidbau.com/archives/2010/03/14/python_pipy_spigot.h... ):

    def pi_decimal_digits():
      q, r, t, j = 1, 180, 60, 2
      while True:
        u, y = 3*(3*j+1)*(3*j+2), (q*(27*j-12)+5*r)//(5*t)
        yield y
        q, r, t, j = 10*q*j*(2*j-1), 10*u*(q*(5*j-2)+r-y*t), t*u, j+1
If you mean that pi can't be written as a number to infinite precision using place-value notation (as opposed to a more useful notation like Python) then I agree that only a finite prefix can ever be observed.
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by lmm on Thursday June 17, 2021 @10:50PM (#27546901)
What you've written is not pi, it's a procedure for computing pi. Python expressions are not a notation, they fail basic requirements for a reasonable notation (for example you cannot generally determine whether two Python expressions are equal or not).
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by mietek on Friday June 18, 2021 @04:58AM (#27548585)
You may find it interesting to learn that one cannot generally determine whether two real numbers are equal or not: equality on real numbers is undecidable.
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by lmm on Friday June 18, 2021 @05:03AM (#27548606)
I'm well aware. It's also the case that there is no good notation for the real numbers; in particular since any given notation system can only represent countably many distinct entities, almost all real numbers will be are unrepresentable in that notation system. Therefore the notion that the full set of reals actually exists is extremely dubious.
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by mcguire on Thursday June 17, 2021 @02:42PM (#27542982)
Note that the Python version of pi requires an unbounded amount of memory and, more importantly, an infinite amount of time to produce pi to infinite precision.
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by Kranar on Thursday June 17, 2021 @10:42PM (#27546857)
Not at all, the reason you may think so is that you're very used to representing numbers using a base 10 number system and in that system it is inherently impossible to represent pi. But if you change how you represent numbers, you can represent pi exactly. What OP did was represent pi using a syntax inspired by a programming language, which is just as valid a number system as any other formal representation as far as correctness goes, although of course as a human I likely would not wish to express most of my use cases involving numbers using a full blown programming language.

That said, one can perform all of arithmetic using that system and represent any property of numbers that could be represented otherwise.

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by chriswarbo on Thursday June 17, 2021 @04:38PM (#27544299)
> Note that the Python version of pi requires an unbounded amount of memory

Really? I measure it as exactly 200 bytes (not counting the 4-space indentation that HackerNews requires, and not including a trailing newline)

> and, more importantly, an infinite amount of time to produce pi to infinite precision

I can see it right now, with infinite precision. If it's taking an infinite amount of time to show up I'd contact your ISP ;)

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by mcguire on Friday June 18, 2021 @04:37PM (#27554753)
Ah, I see where you are going with this. However, I can offer a version which, without loss of generality, gives another 200-to-1 compression (not counting UTF-8 multibytes): π.

There it is, in all it's infinite splendor.

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by mensetmanusman on Thursday June 17, 2021 @06:06PM (#27544948)
Also, pi = C/d

in geometry notation :)