There are all sorts of hierarchies and classes of computing models that are “infinite” in any of a large set of different ways. However, Gödel’s theorems apply regardless because Gödel’s theorems are about mathematics, not computing.
You can in principle devise extensions of formal systems in which you allow infinite numbers of axioms and/or axiom schemata, but they’re actually boring in many ways. Gödel’s 1st incompleteness theorem doesn’t apply because you can just list every sentence of the complete theory in the axioms. Such a theory still can’t prove its own consistency though, since it can’t even express its own consistency—its infinitely many axioms can’t be expressed in one proposition.
Things get messier when you allow infinitely complex sentences. This is related to some forms of hyper-computation in the sense that any operation on such sentences would require both infinite memory and more computation than a Turing machine. There are theorems analogous to Gödel’s for such infinitary logics, even for arbitrary infinite cardinalities, but also plenty of unresolved problems including somewhat arbitrary choices in how finite logic should be extended to infinitary.
So I can evade Godel’s first Incompleteness theorems if I allow an infinite amount of axioms to prove everything in mathematics, making it complete, but I can’t prove it’s consistency. That’s a nice advantage of hypercomputers and infinite computation.
As I understand it, that point about “somewhat arbitrary choices in how finite logic should be extended to infinitary” would also include, for every one of the infinitely many undecidable-by-a-non-hypercomputer propositions, a free choice of whether to include a proposition or its negation as an axiom. Well, almost. Each freely chosen axiom has infinitely many consequences that are the no longer free choices. But it’s still (countably) infinitely many choices. But if you have countably infinitely many binary choices, that’s like choosing a random real number between 0 and 1, so there are uncountably many ways of making that extension, each of which results in a distinct infinitary system. Your proposed hypercomputer can generate all of these.
Yes, that is one example of many arbitrary choices in infinite systems. In practice that means that you give up the ability to communicate to anyone else which system you’re working with, unless you also have a channel with which to communicate an infinite amount of information to them.
However the somewhat arbitrary choices I was talking about with respect to infinitary logics was about what rules of inference you use to derive new infinite sentences. Even in finitary logic there are choices such as whether to accept proofs that use Law of Excluded Middle, as well as more esoteric principles such as modal logic, relevance logics, and paraconsistency, but when you have sentences with infinitely many clauses (or even more complex structures) then we need rules that aren’t determined by what happens with every finite number of clauses. Some of these might be very counterintuitive when building from an experience with only finitely many terms, but we can’t say they’re wrong.
Yes, that is one example of many arbitrary choices in infinite systems. In practice that means that you give up the ability to communicate to anyone else which system you’re working with, unless you also have a channel with which to communicate an infinite amount of information to them.
Well, that’s trivially simulatable, since I can generate an infinitely large communication channel, so that’s not a constraint.
There are all sorts of hierarchies and classes of computing models that are “infinite” in any of a large set of different ways. However, Gödel’s theorems apply regardless because Gödel’s theorems are about mathematics, not computing.
You can in principle devise extensions of formal systems in which you allow infinite numbers of axioms and/or axiom schemata, but they’re actually boring in many ways. Gödel’s 1st incompleteness theorem doesn’t apply because you can just list every sentence of the complete theory in the axioms. Such a theory still can’t prove its own consistency though, since it can’t even express its own consistency—its infinitely many axioms can’t be expressed in one proposition.
Things get messier when you allow infinitely complex sentences. This is related to some forms of hyper-computation in the sense that any operation on such sentences would require both infinite memory and more computation than a Turing machine. There are theorems analogous to Gödel’s for such infinitary logics, even for arbitrary infinite cardinalities, but also plenty of unresolved problems including somewhat arbitrary choices in how finite logic should be extended to infinitary.
So I can evade Godel’s first Incompleteness theorems if I allow an infinite amount of axioms to prove everything in mathematics, making it complete, but I can’t prove it’s consistency. That’s a nice advantage of hypercomputers and infinite computation.
As I understand it, that point about “somewhat arbitrary choices in how finite logic should be extended to infinitary” would also include, for every one of the infinitely many undecidable-by-a-non-hypercomputer propositions, a free choice of whether to include a proposition or its negation as an axiom. Well, almost. Each freely chosen axiom has infinitely many consequences that are the no longer free choices. But it’s still (countably) infinitely many choices. But if you have countably infinitely many binary choices, that’s like choosing a random real number between 0 and 1, so there are uncountably many ways of making that extension, each of which results in a distinct infinitary system. Your proposed hypercomputer can generate all of these.
Yes, that is one example of many arbitrary choices in infinite systems. In practice that means that you give up the ability to communicate to anyone else which system you’re working with, unless you also have a channel with which to communicate an infinite amount of information to them.
However the somewhat arbitrary choices I was talking about with respect to infinitary logics was about what rules of inference you use to derive new infinite sentences. Even in finitary logic there are choices such as whether to accept proofs that use Law of Excluded Middle, as well as more esoteric principles such as modal logic, relevance logics, and paraconsistency, but when you have sentences with infinitely many clauses (or even more complex structures) then we need rules that aren’t determined by what happens with every finite number of clauses. Some of these might be very counterintuitive when building from an experience with only finitely many terms, but we can’t say they’re wrong.
Well, that’s trivially simulatable, since I can generate an infinitely large communication channel, so that’s not a constraint.