35 ms·

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).
        Retric 6y ago
        Sure, but the poster clearly doesn’t understand if they are saying Therefore you cannot know BB(n) beyond a certain n. I am not really conveying this clearly but people seem to misunderstand that Touring machines are just one class of computers. Just as quantum computers are another class of machines, so to are human minds or x86 processors. You can very much program a touring machine with the output of a different class of computer hardware, but that doesn’t solve the problem. >>> You need an Oracle at runtime not compile time. <<< There that’s what I was missing.

For an n-sized program, run it for BB(n) steps. If it hasn't halted then by definition it will never halt.

# 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).
        Retric 6y ago
        Sure, but the poster clearly doesn’t understand if they are saying Therefore you cannot know BB(n) beyond a certain n. I am not really conveying this clearly but people seem to misunderstand that Touring machines are just one class of computers. Just as quantum computers are another class of machines, so to are human minds or x86 processors. You can very much program a touring machine with the output of a different class of computer hardware, but that doesn’t solve the problem. >>> You need an Oracle at runtime not compile time. <<< There that’s what I was missing.