3 ms·

The halting problem often seems to “block” a lot of approaches to algorithmic information theory and induction that are based upon computable programs. However,

The halting problem often seems to “block” a lot of approaches to algorithmic information theory and induction that are based upon computable programs. However, is there any research on whether the halting problem actually has any sort of material influence on our ability to perform real-world induction? For instance, if an oracle could tell us whether any given monotone universal Turing machine has reached a point in its execution where it will never print anything else to the output tape, would the results of induction using this oracle differ considerably from the case where we simply “skip” to the next program in an exhaustive search of program space after its fails to produce output for n consecutive steps (for sufficiently large n)? I’m referring to induction on cases that are not contrived as edge cases or adversarial examples (e.g., BB(3,3))—just induction on “regular” compressible data.

deleted 3y ago
[deleted]
cubefox 3y ago
I'm not sure this is what you mean but obviously in practice uncomputable problems don't differ from problems which are perfectly computable in theory but far too slow to be computed in practice.
SCHiM 3y ago
I'm a not educated in mathematics, so I can't know for sure if what I'm going to respond to your question is really relevant or not. But here it goes anyway. I'm a security researcher, and I write my own fuzzers. Fuzzers are tools that automatically search for inputs that have security implications for the program that you're testing. They algorithmically generate and mutate inputs, feed them to a program, and observe what happens, tens/hundreds/thousands of times a second. If an input crashes a program you can think of this as "halting" the program. To have a fuzzer that could find any or all bugs in any program you run it on, in a feasible amount of time, would surely involve solving the halting problem I think. And sure, even after billions of tests, people still manage to find bugs in image decoders, so the fuzzers we do have are not flawless. At the same time, I have experienced in the real world that fuzzers manage to penetrate unexpectedly deep into complex programs if given enough time. The validation on input performed by the target under test, the limited memory and storage in a modern PC sort of helps to keep your fuzzer on the rails. Unless cryptography is involved, which are like computational tar-pits for fuzzers. Any well guarded/specified program acts as its own guardrail against needing to solve the halting problem for the fuzzer. It convinced me of the following, regarding the finding of security bugs in programs: 1) Fuzzers are good at targeting programs that perform rigorous input validation, barring cryptography. 2) You don't need a fuzzer for a program that does not perform rigorous input validation (where the fuzzer doesn't necessarily work well.)

deleted 3y ago

[deleted]

cubefox 3y ago

I'm not sure this is what you mean but obviously in practice uncomputable problems don't differ from problems which are perfectly computable in theory but far too slow to be computed in practice.

SCHiM 3y ago

I'm a not educated in mathematics, so I can't know for sure if what I'm going to respond to your question is really relevant or not. But here it goes anyway. I'm a security researcher, and I write my own fuzzers. Fuzzers are tools that automatically search for inputs that have security implications for the program that you're testing. They algorithmically generate and mutate inputs, feed them to a program, and observe what happens, tens/hundreds/thousands of times a second. If an input crashes a program you can think of this as "halting" the program. To have a fuzzer that could find any or all bugs in any program you run it on, in a feasible amount of time, would surely involve solving the halting problem I think. And sure, even after billions of tests, people still manage to find bugs in image decoders, so the fuzzers we do have are not flawless. At the same time, I have experienced in the real world that fuzzers manage to penetrate unexpectedly deep into complex programs if given enough time. The validation on input performed by the target under test, the limited memory and storage in a modern PC sort of helps to keep your fuzzer on the rails. Unless cryptography is involved, which are like computational tar-pits for fuzzers. Any well guarded/specified program acts as its own guardrail against needing to solve the halting problem for the fuzzer. It convinced me of the following, regarding the finding of security bugs in programs: 1) Fuzzers are good at targeting programs that perform rigorous input validation, barring cryptography. 2) You don't need a fuzzer for a program that does not perform rigorous input validation (where the fuzzer doesn't necessarily work well.)