5 ms·

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 funct

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.
      - Retric 6y ago
        Not quite, a BB(n) is just a number so a computer could have a precomputed look up table of them. Just as you can store 7 in a programs source code you could store BB(7). The issue is the halting problem is for a given program and an arbitrary input. If you want to store all BB(n)’s for an arbitrary input in a lookup table you would need an infinite program size. Even if that’s acceptable, reading an infinitely large program + some input into itself takes infinite time.
        lisper 6y ago
        You are missing the point. Simply knowing BB(n) is enough to solve the halting problem for a TM with n states. It doesn't matter whether it is precomputed and stored in a lookup table, or computed on the fly, or revealed to you by God. If you know BB(n) by any means, you can solve the halting problem for a TM with n states. Therefore you cannot know BB(n) beyond a certain n.
        Retric 6y ago
        Very much no, any pattern of code is acceptable in computer science. You don’t need to have a specific class of computer compute the programs running on it. CS even has the idea of an Oracle machine: The problem does not have to be computable; the oracle is not assumed to be a Turing machine or computer program. https://en.wikipedia.org/wiki/Oracle_machine https://en.wikipedia.org/wiki/Oracle_machine It’s a very critical idea in CS. There is no specific BB(1, 2, ... n) that’s suddenly impossible to discover, however writing a program that runs on touring machines that can find arbitrary BB(n)’s isn’t solvable. Another way of saying it is it takes increasing complexity to solve BB(n) as n grows, a given program can only be of finite complexity.
        kd0amg 6y ago
        This entire thread is about how to use a BB oracle to solve halting (and why that means BB is uncomputable).
Aardwolf 6y ago
But of course BB can get dwarfed by other uncomputable functions, like Rayo's: https://googology.wikia.org/wiki/Rayo%27s_number https://googology.wikia.org/wiki/Rayo%27s_number
- deleted 6y ago
  [deleted]
- hnuser123456 6y ago
  That's a lot of words and symbols for some not-very-impressive lower bounds. I present hnuser123456's function: f(n)=n (n Knuth up arrows) n Coming back to Rayo, my number is instead f(10^100) rather than Rayo(10^100), and given the series of lower bounds presented in that article, this should easily dwarf that, unless Rayo's will end up growing Knuth arrows faster than linear. I'm not smart enough to evaluate that though. If it would, wonder if this would beat it: f(n)=n (n Knuth up arrows) n (n Knuth up arrows) n Or n copies of n Knuth up arrows...
  - FartyMcFarter 6y ago
    Knuth up arrows are computable functions, right? So they can't possibly grow faster than BB(n), let alone even faster-growing functions.
    - hnuser123456 6y ago
      Must be. Since Rayo(10000)>2↑↑↑65536 it seemed easy to spam a lot more up arrows there (10k of them), but the tide probably changes after n grows by another 95 orders of magnitude. Wonder where Rayo's function intersects mine.
      - Aardwolf 6y ago
        Rayo's function can describe the idea of "f(n)=n (n Knuth up arrows) n" with relatively few symbols - just like your post did using relatively few characters
  - 6y ago

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.
    - Retric 6y ago
      Not quite, a BB(n) is just a number so a computer could have a precomputed look up table of them. Just as you can store 7 in a programs source code you could store BB(7). The issue is the halting problem is for a given program and an arbitrary input. If you want to store all BB(n)’s for an arbitrary input in a lookup table you would need an infinite program size. Even if that’s acceptable, reading an infinitely large program + some input into itself takes infinite time.
      - lisper 6y ago
        You are missing the point. Simply knowing BB(n) is enough to solve the halting problem for a TM with n states. It doesn't matter whether it is precomputed and stored in a lookup table, or computed on the fly, or revealed to you by God. If you know BB(n) by any means, you can solve the halting problem for a TM with n states. Therefore you cannot know BB(n) beyond a certain n.
        Retric 6y ago
        Very much no, any pattern of code is acceptable in computer science. You don’t need to have a specific class of computer compute the programs running on it. CS even has the idea of an Oracle machine: The problem does not have to be computable; the oracle is not assumed to be a Turing machine or computer program. https://en.wikipedia.org/wiki/Oracle_machine https://en.wikipedia.org/wiki/Oracle_machine It’s a very critical idea in CS. There is no specific BB(1, 2, ... n) that’s suddenly impossible to discover, however writing a program that runs on touring machines that can find arbitrary BB(n)’s isn’t solvable. Another way of saying it is it takes increasing complexity to solve BB(n) as n grows, a given program can only be of finite complexity.
        kd0amg 6y ago
        This entire thread is about how to use a BB oracle to solve halting (and why that means BB is uncomputable).

Aardwolf 6y ago

But of course BB can get dwarfed by other uncomputable functions, like Rayo's: https://googology.wikia.org/wiki/Rayo%27s_number https://googology.wikia.org/wiki/Rayo%27s_number

deleted 6y ago
[deleted]
hnuser123456 6y ago
That's a lot of words and symbols for some not-very-impressive lower bounds. I present hnuser123456's function: f(n)=n (n Knuth up arrows) n Coming back to Rayo, my number is instead f(10^100) rather than Rayo(10^100), and given the series of lower bounds presented in that article, this should easily dwarf that, unless Rayo's will end up growing Knuth arrows faster than linear. I'm not smart enough to evaluate that though. If it would, wonder if this would beat it: f(n)=n (n Knuth up arrows) n (n Knuth up arrows) n Or n copies of n Knuth up arrows...
- FartyMcFarter 6y ago
  Knuth up arrows are computable functions, right? So they can't possibly grow faster than BB(n), let alone even faster-growing functions.
  - hnuser123456 6y ago
    Must be. Since Rayo(10000)>2↑↑↑65536 it seemed easy to spam a lot more up arrows there (10k of them), but the tide probably changes after n grows by another 95 orders of magnitude. Wonder where Rayo's function intersects mine.
    - Aardwolf 6y ago
      Rayo's function can describe the idea of "f(n)=n (n Knuth up arrows) n" with relatively few symbols - just like your post did using relatively few characters
- 6y ago