I imagine you are refering to a Turing Machine halting or not halting.
There are statements in Set Theory, which Turing Machines cannot interpret at all ( formally, they have a particular complexity), and require the introduction of “Oracles” in order to assist in interpreting. These are called Oracle Turing Machines. They come about frequently in Descriptive Set Theory.
So we can, in a manner of speaking, encode them as programs to be run in a Turing Machine with a oracle tape. That’s not too hard to do, once we use stronger models of computation, and thus we can still encode set theory statements in more powerful computers.
So I’m still basically right, philosophically speaking, in that we can always encode set theory/mathematics statements in a program, using the trick I described of converting set theory into quantified statements, and then looking at the first quantifier to determine whether halting or not-halting is either true or false.
You would be right in most cases. But, there is still the issue of independent statements. ” ZF is consistent” can not be shown to be true or false, if ZF is consistent, via the Incompleteness Theorems.
So, some statements may not be shown to halting, or not halting. Which, is the famous halting problem.
Any algorithm would be unable to tell you, if the statement halts or doesn’t halt. So, not all statements can be expressed as true/false or halt/not-halt
I didn’t say that it had to return an answer, and the halting problem issue for Turing Machines is essentially that even though a program halts or doesn’t halt, which in this case can be mapped to true or false, we don’t have an algorithm that runs on a Turing Machine that can always tell us which of the 2 cases is true.
Gödel’s incompleteness theorems are important, but in this context, we can basically enhance the definition of a computer philosophically to solve essentially arbitrary problems, and the validity problem of first order logic becomes solvable by introducing an Oracle tape or a closed timeline curve to a Turing Machine, and at that point we can decide the validity and satisfiability problems of first order logic.
You also mentioned that oracles like oracle tapes can provide the necessary interpretation for set theory statements to be encoded, which was my goal, since a Turing Machine or other computer with an Oracle tape, which gets around the first incompleteness theorem by violating an assumption necessary to get the result.
Thank you for clarifying, I misunderstood your post.
Yes, you’re right. “essentially” arbitrary problems would be free game.
There is a hierarchy of questions one can ask though. That is, whatever oracle you introduce, you can now ask more complex questions and would require a more complex oracle to answer ( basically, you can ask the first oracle, questions about itself, which require another more complex oracle to answer).
When I saw you use the word “computer” I thought you meant, a literal computer that we could in principle build.
My focus was on the more philosophical/impractical side, and the computers we can actually build in principle, assuming the laws of physics are unchangable and we are basically correct, we can’t even build Universal Turing Machines/Turing Complete systems, but just linear bounded automatons, due to the holographic principle.
Also, the entire hierarchy can be solved simply by allowing non-uniform computational models, which is yet another benefit of non-uniform computational models.
I imagine you are refering to a Turing Machine halting or not halting.
There are statements in Set Theory, which Turing Machines cannot interpret at all ( formally, they have a particular complexity), and require the introduction of “Oracles” in order to assist in interpreting. These are called Oracle Turing Machines. They come about frequently in Descriptive Set Theory.
So we can, in a manner of speaking, encode them as programs to be run in a Turing Machine with a oracle tape. That’s not too hard to do, once we use stronger models of computation, and thus we can still encode set theory statements in more powerful computers.
So I’m still basically right, philosophically speaking, in that we can always encode set theory/mathematics statements in a program, using the trick I described of converting set theory into quantified statements, and then looking at the first quantifier to determine whether halting or not-halting is either true or false.
You would be right in most cases. But, there is still the issue of independent statements. ” ZF is consistent” can not be shown to be true or false, if ZF is consistent, via the Incompleteness Theorems.
So, some statements may not be shown to halting, or not halting. Which, is the famous halting problem.
Any algorithm would be unable to tell you, if the statement halts or doesn’t halt. So, not all statements can be expressed as true/false or halt/not-halt
There are 2 things to be said here:
I didn’t say that it had to return an answer, and the halting problem issue for Turing Machines is essentially that even though a program halts or doesn’t halt, which in this case can be mapped to true or false, we don’t have an algorithm that runs on a Turing Machine that can always tell us which of the 2 cases is true.
Gödel’s incompleteness theorems are important, but in this context, we can basically enhance the definition of a computer philosophically to solve essentially arbitrary problems, and the validity problem of first order logic becomes solvable by introducing an Oracle tape or a closed timeline curve to a Turing Machine, and at that point we can decide the validity and satisfiability problems of first order logic.
You also mentioned that oracles like oracle tapes can provide the necessary interpretation for set theory statements to be encoded, which was my goal, since a Turing Machine or other computer with an Oracle tape, which gets around the first incompleteness theorem by violating an assumption necessary to get the result.
Thank you for clarifying, I misunderstood your post.
Yes, you’re right. “essentially” arbitrary problems would be free game.
There is a hierarchy of questions one can ask though. That is, whatever oracle you introduce, you can now ask more complex questions and would require a more complex oracle to answer ( basically, you can ask the first oracle, questions about itself, which require another more complex oracle to answer).
When I saw you use the word “computer” I thought you meant, a literal computer that we could in principle build.
My focus was on the more philosophical/impractical side, and the computers we can actually build in principle, assuming the laws of physics are unchangable and we are basically correct, we can’t even build Universal Turing Machines/Turing Complete systems, but just linear bounded automatons, due to the holographic principle.
Also, the entire hierarchy can be solved simply by allowing non-uniform computational models, which is yet another benefit of non-uniform computational models.