9 ms·

How the Slowest Computer Programs Illuminate Math’s Fundamental Limits

154 points by pontus 6y ago

cft 6y ago
I wonder how one goes about proving that such large computations as BB(27) are physically impossible in our universe?
- cjfd 6y ago
  If a computation goes through N states before completing the universe in which it takes place has to have at least N possible states. One theory (https://en.wikipedia.org/wiki/Bekenstein_bound https://en.wikipedia.org/wiki/Bekenstein_bound) would state that the possible number of bits of information in a universe with radius R is the surface of the sphere 4 * pi * R^2 expressed in Planck units. This gives a limit to how many states this universe can have.
  - cft 6y ago
    But the number of states N required for BB(27) could be (much?) smaller than the number of steps of BB(27)?
    - tialaramex 6y ago
      Nope. Suppose that say, state #16 and state #416 are in fact identical. Well then this machine does not halt, as of course being in this state leads back to the same state again in just four hundred moves, state #17 and #417 and so on will be the same too. The notional paper tape might have identical states, but if this happens in a machine that does eventually halt the rest of the machine state must be different, and these are both state that a universe must keep in order to instantiate the machine.
    - JoshTriplett 6y ago
      Different senses of the word "state". Such a machine could have fewer state-machine states than steps, but the overall state of the machine (including all its auxiliary storage) must never repeat, or it's in a loop and will never terminate. And BB machines must terminate, by definition.
      - cft 6y ago
        Yes, I should have thought more about it. So these BB(N) numbers are direct complexity bounds on various mathematical statements.
    - chalst 6y ago
      Smaller, yes: if a TM uses n bits of space, its execution time can exceed any polynomial of n in steps. But any such space-bounded deterministic computation that takes 2^n steps will not terminate, by exhaustion of possible state transitions, and nontermination would mean it does not compute a function over all inputs. This constraint is small in terms of the kind of growth functions this kind of maths deals with.
sgfyd 6y ago
> Nevertheless, that incomprehensibly huge number is still an exact figure whose magnitude, according to Aaronson, represents “a statement about our current knowledge” of number theory. This is, of course, contradicted later in the article in which they point out that `BB(800)` (or so) has been proved independent of ZFC; there's no really good reason to believe `BB(27)` is not likewise independent. There may still be a truth of the matter about the value of `BB(800)` or `BB(27)` (as the case may be), since ZFC hardly encompasses all truth, but calling such a number an "exact figure" is a bit like claiming to know the birth date of Julius Caesar down to the millisecond: Implausible to start with, and the closer you look the more you wonder, "what does the question even mean? Relative to what standard?" (In the one case, "of time"; in the other, "of mathematical truth".)
- tromp 6y ago
  > There may still be a truth of the matter about the value of `BB(800)` The reason for independence of ZFC is that ZFC fails to prove "TM M doesn't halt", for some non-halting 800-state Turing Machine M. It has no problem proving the halting of the busy beaver machine in BB(800) steps. Unlike the birth-time of Caesar, BB(800) is still well-defined and an "exact figure", because we consider the notion of whether any particular Turing Machine halts or not to be well-defined.
  - ifdefdebug 6y ago
    So does this mean that "the machine that halts if ZF is inconsistent" is guaranteed to not halt (and not loop) in less than BB(748) steps? Or would it be possible for some crazy billionaire to throw immensurable amounts of computing power at the problem and run the machine just to, after a few years, wake up one morning, find that his machine has halted, and tell the world he had proved ZFC to be inconsistent? Likewise, could he wake up one morning, find his machine caught in an infinite loop, and tell the world "hey, I just proved this machine will never halt, so I proved ZF to be consistent, quod est adsurdum so better forget about ZFC...
    - tromp 6y ago
pkrumins 6y ago
I created the visualization for this story by running BB(5). You can find the source code (a full Turing Machine implementation that runs BB) and visualizations of other BBs in my blog post https://catonmat.net/busy-beaver https://catonmat.net/busy-beaver.
tromp 6y ago
> The busy beaver game is all about the behavior of Turing machines A busy beaver for lambda calculus is even easier to define: the maximum normal form size of any closed lambda term of size n (or 0 if none exists). The series [1] starts as 0, 0, 0, 4, 0, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 22, 24, 26, 30, 42, 52, 44, 58, 223, 160, 267, 298, 1812, 327686, 38127987424941, 578960446186580977117854925043439539266349923328202820197287920039565648199686 Results are more fine grained than for TMs because these sizes are in units of bits (lambda and application measuring as 2 bits, and a variable bound by n'th enclosing lambda as n+1 bits). Graham's number is surpassed within 114 bits, while the smallest known TM for surpassing it takes 225 bits to describe. [1] https://oeis.org/A333479 https://oeis.org/A333479
- bryan0 6y ago
  Cool. What are the first few lambda terms in the sequence?
  - tromp 6y ago
    Here's the initial output of a Haskell program used to find them (courtesy of Bertram Felgenhauer): 4: \1 6: \\1 7: \\2 8: \\\1 9: \\\2 10: \\\\1 11: \\\\2 12: \\\\\1 13: \\\\\2 14: \\\\\\1 15: \\\\\\2 16: \\\\\\\1 17: \\\\\\\2 18: \\\\\\\\1 19: \\\\\\\\2 20: \\\\\\\\\1 21: \(\1 1) (1 (\2)) A few more are given in [1]. [1] https://mathoverflow.net/questions/353514/whats-the-smallest-lambda-calculus-term-not-known-to-have-a-normal-form https://mathoverflow.net/questions/353514/whats-the-smallest...
chalst 6y ago
Andrej Bauer: Is it just me, or is the busy-beaver function a figment of classical mathematics? https://twitter.com/andrejbauer/status/1327670607824252928 https://twitter.com/andrejbauer/status/1327670607824252928
- qsort 6y ago
  What does he mean by that? (not criticism, I genuinely don't understand).
  - chriswarbo 6y ago
    There is a distinction between "constructive" mathematics (AKA "intuitionistic") and "non-constructive" mathematics (AKA "classical"). In constructive mathematics, the only way to prove that something (e.g. a number) exists is to give an algorithm that constructs it. We can do this in classical mathematics too (roughly speaking, it's a super-set of constructive mathematics); but we can also prove that something exists in another way: by disproving that it doesn't exist (i.e. a double negative). In other words, classical mathematics lets us use a proof of 'not(not(X))' as a proof of 'X'. There are some other ways to express this, which are essentially equivalent; e.g. the "law of the excluded middle" 'for all X, either X is true or not(X) is true'. These proof steps are not constructive, since knowing that not(X) is false doesn't tell us how to actually find/construct X. Likewise, the law of the excluded middle is like writing an if/then/else statement where both branches will arrive at the same result, but it doesn't tell us which of those branches to take. We usually talk about proofs being constructive or non-constructive, rather than values (e.g. numbers). A constructivist shouldn't agree with a non-constructive proof, but they should agree with an alternative, constructive proof of the same result. The interesting philosophical question being made here is: if a value's existence can only be proved non-constructively, should constructivists disbelieve in that value? In this case that value is the busy-beaver function: it can't be defined constructively, since no algorithm can decide the halting problem.
    - chalst 6y ago
      This is a good explanation. I just have one quibble: the school of constructivism that Andrej follows is not the only one; there is a Russian school that accepts Markov's principle, which is essentially the logical counterpart of the idea that there is a fact of the matter whether a deterministic Turing computation terminates. I don't know if constructivists from the Russian school allow BB to be definable, but the argument for it to be undefined is trickier on this account. https://en.wikipedia.org/wiki/Markov%27s_principle https://en.wikipedia.org/wiki/Markov%27s_principle
FartyMcFarter 6y ago
One fascinating thing about the function BB(n) is that it grows faster than any computable function. The proof of this is simple: if you had a computable function f(n), and f(n) >= BB(n) for all values of n, you could use that to solve the halting problem, which in itself is impossible. I used to implicitly assume that we can make concrete, closed-form, functions that grow as fast as we want them to. The above shows that this is clearly false.
- kzrdude 6y ago
  How would you use it to solve the halting problem?
  - boloust 6y ago
    For an n-sized program, run it for BB(n) steps. If it hasn't halted then by definition it will never halt.
  - FartyMcFarter 6y ago
    # Assuming f(n) >= BB(n) def does_it_halt (m: turing_machine): n_steps = f(count_states(m)) for i in range (n_steps): run(m) return is_in_halting_state(m) The key point is that if you know that all machines with n states halt in BB(n) steps at most (or will otherwise never halt), you just need to run any of those machines for BB(n) steps and then check if they already halted or not.
    - Retric 6y ago
      The tricky bit is proving BB(n) doesn’t solve the halting problem. Otherwise feed program of n size and run it for BB(n) + 1 steps and it’s stuck in a loop.
      - FartyMcFarter 6y ago
        I'm not sure what you mean. Having a computable version of BB(n) for all n does solve the halting problem, which is why it's impossible to compute with any existing computer. If you run a program with n states for BB(n) + 1 steps it will either already have halted, or it will never halt. This is by definition.
monster_group 6y ago
After reading this kind of fascinating stuff, I feel ashamed that I am wasting the opportunity of having a human mind by writing CRUD applications (though I am nowhere near as smart as this stuff requires one to be - I can barely clear whiteboard coding interviews).
fjfaase 6y ago
Very interesting. In the past, I spend some time on finding the largest number that could be calculated by a Brainfuck program when the memory cells can hold arbitrary large numbers (and not be restricted to bytes as with the official language). It takes a bit longer to take-off. For my findings, see: https://www.iwriteiam.nl/Ha_bf_numb.html https://www.iwriteiam.nl/Ha_bf_numb.html
lisper 6y ago
> 6,561 possible machines with two rules Huh? How do they get to that number? A TM state can be described with 4+2log2(N) bits, where N is the number of states, so a 2-state TM can be specified with 12 bits, so there are at most 4096 of them. Where do the extra 2465 come from?
- tromp 6y ago
  They can be described with 2n * log(4(n + 1)) bits, since each of the n states has two rules, and each rule specifies a new binary symbol, a left or right direction, and a new state which can also be the halt state. For n=2, this gives 12^4 = 20736 machines. I have no idea where the number 6561 comes from.
  - lisper 6y ago
    Right. I forgot about the halt state. But yeah, 6561 (=3^8) still looks mighty hinky.
  - cedilla 6y ago
    A052200[1] lists the number of possible Turing machines and it agrees with you. I found no sequence containing 6561 and either "Turing" or "beaver" that illuminated me to where that number came from. 1: https://oeis.org/A052200 https://oeis.org/A052200
- tzs 6y ago
  Probably its a 3 symbol Turing machine (0, 1, blank). For each rule, there are 3 possible inputs (0, 1, blank), 3 possible outputs (0, 1, blank), 3 possible movements (left, right, stay), and 3 possible next rules (rule 1, rule 2, halt). That gives 3^4 possible rules, or 3^4 3^4 = 3^8 = 6561 possible pairs of rules.
  - lisper 6y ago
    Nope, that's not it. See the sibling comment from xjparker.
- xjparker 6y ago
dandanua 6y ago
> If you knew all the busy beaver numbers, then you could settle all of those questions. A lot of important questions in number theory could be answered, but not all. For example, the mentioned Collatz conjecture (3n+1) is of different type. To prove this conjecture you need to prove the halting for EVERY argument. Checking halting of a single program will not be enough, so busy beaver won't help. This is a next level task in the Arithmetical Hierarchy [1]. Though, in fact, you can define the next level Busy Beaver that could solve Collatz conjecture. To solve more complicated problems you need high-order Busy Beavers. [1] https://en.wikipedia.org/wiki/Arithmetical_hierarchy https://en.wikipedia.org/wiki/Arithmetical_hierarchy
earthboundkid 6y ago
I too have read Scott Aaronson's blog.

154 points by pontus 6y ago

cft 6y ago

I wonder how one goes about proving that such large computations as BB(27) are physically impossible in our universe?

cjfd 6y ago
If a computation goes through N states before completing the universe in which it takes place has to have at least N possible states. One theory (https://en.wikipedia.org/wiki/Bekenstein_bound https://en.wikipedia.org/wiki/Bekenstein_bound) would state that the possible number of bits of information in a universe with radius R is the surface of the sphere 4 * pi * R^2 expressed in Planck units. This gives a limit to how many states this universe can have.
- cft 6y ago
  But the number of states N required for BB(27) could be (much?) smaller than the number of steps of BB(27)?
  - tialaramex 6y ago
    Nope. Suppose that say, state #16 and state #416 are in fact identical. Well then this machine does not halt, as of course being in this state leads back to the same state again in just four hundred moves, state #17 and #417 and so on will be the same too. The notional paper tape might have identical states, but if this happens in a machine that does eventually halt the rest of the machine state must be different, and these are both state that a universe must keep in order to instantiate the machine.
  - JoshTriplett 6y ago
    Different senses of the word "state". Such a machine could have fewer state-machine states than steps, but the overall state of the machine (including all its auxiliary storage) must never repeat, or it's in a loop and will never terminate. And BB machines must terminate, by definition.
    - cft 6y ago
      Yes, I should have thought more about it. So these BB(N) numbers are direct complexity bounds on various mathematical statements.
  - chalst 6y ago
    Smaller, yes: if a TM uses n bits of space, its execution time can exceed any polynomial of n in steps. But any such space-bounded deterministic computation that takes 2^n steps will not terminate, by exhaustion of possible state transitions, and nontermination would mean it does not compute a function over all inputs. This constraint is small in terms of the kind of growth functions this kind of maths deals with.

sgfyd 6y ago

> Nevertheless, that incomprehensibly huge number is still an exact figure whose magnitude, according to Aaronson, represents “a statement about our current knowledge” of number theory. This is, of course, contradicted later in the article in which they point out that `BB(800)` (or so) has been proved independent of ZFC; there's no really good reason to believe `BB(27)` is not likewise independent. There may still be a truth of the matter about the value of `BB(800)` or `BB(27)` (as the case may be), since ZFC hardly encompasses all truth, but calling such a number an "exact figure" is a bit like claiming to know the birth date of Julius Caesar down to the millisecond: Implausible to start with, and the closer you look the more you wonder, "what does the question even mean? Relative to what standard?" (In the one case, "of time"; in the other, "of mathematical truth".)

tromp 6y ago
> There may still be a truth of the matter about the value of `BB(800)` The reason for independence of ZFC is that ZFC fails to prove "TM M doesn't halt", for some non-halting 800-state Turing Machine M. It has no problem proving the halting of the busy beaver machine in BB(800) steps. Unlike the birth-time of Caesar, BB(800) is still well-defined and an "exact figure", because we consider the notion of whether any particular Turing Machine halts or not to be well-defined.
- ifdefdebug 6y ago
  So does this mean that "the machine that halts if ZF is inconsistent" is guaranteed to not halt (and not loop) in less than BB(748) steps? Or would it be possible for some crazy billionaire to throw immensurable amounts of computing power at the problem and run the machine just to, after a few years, wake up one morning, find that his machine has halted, and tell the world he had proved ZFC to be inconsistent? Likewise, could he wake up one morning, find his machine caught in an infinite loop, and tell the world "hey, I just proved this machine will never halt, so I proved ZF to be consistent, quod est adsurdum so better forget about ZFC...
  - tromp 6y ago

pkrumins 6y ago

I created the visualization for this story by running BB(5). You can find the source code (a full Turing Machine implementation that runs BB) and visualizations of other BBs in my blog post https://catonmat.net/busy-beaver https://catonmat.net/busy-beaver.

tromp 6y ago

> The busy beaver game is all about the behavior of Turing machines A busy beaver for lambda calculus is even easier to define: the maximum normal form size of any closed lambda term of size n (or 0 if none exists). The series [1] starts as 0, 0, 0, 4, 0, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 22, 24, 26, 30, 42, 52, 44, 58, 223, 160, 267, 298, 1812, 327686, 38127987424941, 578960446186580977117854925043439539266349923328202820197287920039565648199686 Results are more fine grained than for TMs because these sizes are in units of bits (lambda and application measuring as 2 bits, and a variable bound by n'th enclosing lambda as n+1 bits). Graham's number is surpassed within 114 bits, while the smallest known TM for surpassing it takes 225 bits to describe. [1] https://oeis.org/A333479 https://oeis.org/A333479

bryan0 6y ago
Cool. What are the first few lambda terms in the sequence?
- tromp 6y ago
  Here's the initial output of a Haskell program used to find them (courtesy of Bertram Felgenhauer): 4: \1 6: \\1 7: \\2 8: \\\1 9: \\\2 10: \\\\1 11: \\\\2 12: \\\\\1 13: \\\\\2 14: \\\\\\1 15: \\\\\\2 16: \\\\\\\1 17: \\\\\\\2 18: \\\\\\\\1 19: \\\\\\\\2 20: \\\\\\\\\1 21: \(\1 1) (1 (\2)) A few more are given in [1]. [1] https://mathoverflow.net/questions/353514/whats-the-smallest-lambda-calculus-term-not-known-to-have-a-normal-form https://mathoverflow.net/questions/353514/whats-the-smallest...

chalst 6y ago

Andrej Bauer: Is it just me, or is the busy-beaver function a figment of classical mathematics? https://twitter.com/andrejbauer/status/1327670607824252928 https://twitter.com/andrejbauer/status/1327670607824252928

qsort 6y ago
What does he mean by that? (not criticism, I genuinely don't understand).
- chriswarbo 6y ago
  There is a distinction between "constructive" mathematics (AKA "intuitionistic") and "non-constructive" mathematics (AKA "classical"). In constructive mathematics, the only way to prove that something (e.g. a number) exists is to give an algorithm that constructs it. We can do this in classical mathematics too (roughly speaking, it's a super-set of constructive mathematics); but we can also prove that something exists in another way: by disproving that it doesn't exist (i.e. a double negative). In other words, classical mathematics lets us use a proof of 'not(not(X))' as a proof of 'X'. There are some other ways to express this, which are essentially equivalent; e.g. the "law of the excluded middle" 'for all X, either X is true or not(X) is true'. These proof steps are not constructive, since knowing that not(X) is false doesn't tell us how to actually find/construct X. Likewise, the law of the excluded middle is like writing an if/then/else statement where both branches will arrive at the same result, but it doesn't tell us which of those branches to take. We usually talk about proofs being constructive or non-constructive, rather than values (e.g. numbers). A constructivist shouldn't agree with a non-constructive proof, but they should agree with an alternative, constructive proof of the same result. The interesting philosophical question being made here is: if a value's existence can only be proved non-constructively, should constructivists disbelieve in that value? In this case that value is the busy-beaver function: it can't be defined constructively, since no algorithm can decide the halting problem.
  - chalst 6y ago
    This is a good explanation. I just have one quibble: the school of constructivism that Andrej follows is not the only one; there is a Russian school that accepts Markov's principle, which is essentially the logical counterpart of the idea that there is a fact of the matter whether a deterministic Turing computation terminates. I don't know if constructivists from the Russian school allow BB to be definable, but the argument for it to be undefined is trickier on this account. https://en.wikipedia.org/wiki/Markov%27s_principle https://en.wikipedia.org/wiki/Markov%27s_principle

FartyMcFarter 6y ago

One fascinating thing about the function BB(n) is that it grows faster than any computable function. The proof of this is simple: if you had a computable function f(n), and f(n) >= BB(n) for all values of n, you could use that to solve the halting problem, which in itself is impossible. I used to implicitly assume that we can make concrete, closed-form, functions that grow as fast as we want them to. The above shows that this is clearly false.

kzrdude 6y ago
How would you use it to solve the halting problem?
- boloust 6y ago
  For an n-sized program, run it for BB(n) steps. If it hasn't halted then by definition it will never halt.
- FartyMcFarter 6y ago
  # Assuming f(n) >= BB(n) def does_it_halt (m: turing_machine): n_steps = f(count_states(m)) for i in range (n_steps): run(m) return is_in_halting_state(m) The key point is that if you know that all machines with n states halt in BB(n) steps at most (or will otherwise never halt), you just need to run any of those machines for BB(n) steps and then check if they already halted or not.
  - Retric 6y ago
    The tricky bit is proving BB(n) doesn’t solve the halting problem. Otherwise feed program of n size and run it for BB(n) + 1 steps and it’s stuck in a loop.
    - FartyMcFarter 6y ago
      I'm not sure what you mean. Having a computable version of BB(n) for all n does solve the halting problem, which is why it's impossible to compute with any existing computer. If you run a program with n states for BB(n) + 1 steps it will either already have halted, or it will never halt. This is by definition.

monster_group 6y ago

After reading this kind of fascinating stuff, I feel ashamed that I am wasting the opportunity of having a human mind by writing CRUD applications (though I am nowhere near as smart as this stuff requires one to be - I can barely clear whiteboard coding interviews).

fjfaase 6y ago

Very interesting. In the past, I spend some time on finding the largest number that could be calculated by a Brainfuck program when the memory cells can hold arbitrary large numbers (and not be restricted to bytes as with the official language). It takes a bit longer to take-off. For my findings, see: https://www.iwriteiam.nl/Ha_bf_numb.html https://www.iwriteiam.nl/Ha_bf_numb.html

lisper 6y ago

> 6,561 possible machines with two rules Huh? How do they get to that number? A TM state can be described with 4+2log2(N) bits, where N is the number of states, so a 2-state TM can be specified with 12 bits, so there are at most 4096 of them. Where do the extra 2465 come from?

tromp 6y ago
They can be described with 2n * log(4(n + 1)) bits, since each of the n states has two rules, and each rule specifies a new binary symbol, a left or right direction, and a new state which can also be the halt state. For n=2, this gives 12^4 = 20736 machines. I have no idea where the number 6561 comes from.
- lisper 6y ago
  Right. I forgot about the halt state. But yeah, 6561 (=3^8) still looks mighty hinky.
- cedilla 6y ago
  A052200[1] lists the number of possible Turing machines and it agrees with you. I found no sequence containing 6561 and either "Turing" or "beaver" that illuminated me to where that number came from. 1: https://oeis.org/A052200 https://oeis.org/A052200
tzs 6y ago
Probably its a 3 symbol Turing machine (0, 1, blank). For each rule, there are 3 possible inputs (0, 1, blank), 3 possible outputs (0, 1, blank), 3 possible movements (left, right, stay), and 3 possible next rules (rule 1, rule 2, halt). That gives 3^4 possible rules, or 3^4 3^4 = 3^8 = 6561 possible pairs of rules.
- lisper 6y ago
  Nope, that's not it. See the sibling comment from xjparker.
xjparker 6y ago

dandanua 6y ago

> If you knew all the busy beaver numbers, then you could settle all of those questions. A lot of important questions in number theory could be answered, but not all. For example, the mentioned Collatz conjecture (3n+1) is of different type. To prove this conjecture you need to prove the halting for EVERY argument. Checking halting of a single program will not be enough, so busy beaver won't help. This is a next level task in the Arithmetical Hierarchy [1]. Though, in fact, you can define the next level Busy Beaver that could solve Collatz conjecture. To solve more complicated problems you need high-order Busy Beavers. [1] https://en.wikipedia.org/wiki/Arithmetical_hierarchy https://en.wikipedia.org/wiki/Arithmetical_hierarchy

earthboundkid 6y ago

I too have read Scott Aaronson's blog.