Not really. What Godel’s incompleteness theorem basically says is that no effective method that is Turing powerful can prove all truths about the natural numbers. However, in certain other models of computation, we can decide the truth of all natural numbers, and really any statement in first order logic can be decided if they are valid or not. You are overstating the results.
Similarly, the halting problem is solely unsolvable by Turing Machines. There’s another issue, in that even oracles for the halting problem cannot solve their own halting problems, but it turns out that the basic issue is we assumed that computers had to be uniform, that is a single machine/circuit could solve all input sizes of a problem.
If we allow non-uniform circuits or advice strings, then we can indeed compose different circuits for different input sizes to make a logically omnisicent machine. Somewhat similarly, if we can somehow get an advice string or precompute what we need to test before testing it, we can again make a logically omnisicent machine.
Note that I’m only arguing that it makes logical sense to assume logical omnisicence, I’m not arguing it’s useful or that it makes physical sense to do so. (I generally think it’s not too useful, because then you can solve every problem if we assume logical omnisicence, and we thus have assumed away the constraints that are taut in real life.)
The proof that a probabilistic machine with probabilistic advice and a CTC can solve every language is in this paper, albeit it’s several pages down.
Not really. What Godel’s incompleteness theorem basically says is that no effective method that is Turing powerful can prove all truths about the natural numbers. However, in certain other models of computation, we can decide the truth of all natural numbers, and really any statement in first order logic can be decided if they are valid or not. You are overstating the results.
Similarly, the halting problem is solely unsolvable by Turing Machines. There’s another issue, in that even oracles for the halting problem cannot solve their own halting problems, but it turns out that the basic issue is we assumed that computers had to be uniform, that is a single machine/circuit could solve all input sizes of a problem.
If we allow non-uniform circuits or advice strings, then we can indeed compose different circuits for different input sizes to make a logically omnisicent machine. Somewhat similarly, if we can somehow get an advice string or precompute what we need to test before testing it, we can again make a logically omnisicent machine.
Note that I’m only arguing that it makes logical sense to assume logical omnisicence, I’m not arguing it’s useful or that it makes physical sense to do so. (I generally think it’s not too useful, because then you can solve every problem if we assume logical omnisicence, and we thus have assumed away the constraints that are taut in real life.)
The proof that a probabilistic machine with probabilistic advice and a CTC can solve every language is in this paper, albeit it’s several pages down.
https://arxiv.org/abs/0808.2669
Similarly, the proof that a Turing Machine + CTC can solve the halting problem is in this paper below:
https://arxiv.org/abs/1609.05507
Good point! I think what I actually wanted was just the simpler omnipotence paradox.