To clarify: I agree that BSS machines can answer second order questions (maybe not the full analytic hierarchy; that’s something I’ll think more about). My confusion is about this:
The infinite state Turing Machine explicitly computes every function from the natural numbers to the natural numbers, which means they can compute any arithmetical question, no matter how large the n-th order arithmetic question gets.
where you said that it all nth-order arithmetic questions can be decided by some such machine. My above comment was why I believed that the questions that are being answered strike me as second order.
Edit for clarifying the relevance here: it strikes me as plausible that questions about BSS machines halting/not halting have inherent truth; if this would imply that third-order arithmetical questions like CH have inherent truth, I would be surprised and update my view about mathematical truth.
The reasoning is pretty similar to the second order case, and the reason here is that no matter how many orders we add to arithmetic like first-order, second-order, nth order, formal languages and theories are always constrained by the usual definition to countably infinite sets of statements and languages, and the ability to compute any function from N to N means that you have an uncountably infinite set of functions to compute, which is always larger than any individual formal languages and theories in the usual definition.
Now that the original comment has changed, I’m more unsure about what you exactly you mean. Can you be more precise about what you mean by being able to compute arbitrary nth-order arithmetical statements? Is there a BSS machine that halts if and only if CH is true? Is there a BSS machine that halts if and only if there’s a choice function on the set of non-empty subsets of R?
I admit, I haven’t found any such explicit examples yet.
I wish this was more of a common practice to give explicit examples of these mathematical statements in more computational terms.
For the Nth order arithmetical statement issue, what I’m talking about is essentially a generalization of the arithmetical hierarchy, where there’s 0 1, 0 2, 0 3 and so on defined here, until it stops at 0^w, which then continues on the analytical hierarchy from 1 1, 1 2, 1 3, until it too stops at 1^w, which can go on essentially forever.
Essentially, I’m talking about this in a generalized form:
The formal reason why a BSS machine can compute all of this comes down, in the end to the fact that it can compute every function from the natural numbers to the natural numbers, which as a set is always larger than any arithmetical hierarchy, which means that the claim that we can always compute nth order arithmetic for any N follows easily.
So I didn’t mean to clarify what you meant by nth-order statements, but rather that BSS statements can decide them, because that seems way too strong to be true. I’m also a bit more skeptical because:
which then continues on the analytical hierarchy
is not true; the first level of the analytic hierarchy sits on top of the hyperarithmetic hierarchy. And my understanding is that finding a way to have an analagous picture of going from something like a “hyperanalytic hierarchy” to the bottom level of third order arithmetic is something highly non-trivial/impossible/ill-defined, but this isn’t my area of math. So I think it’s easier to ignore the hierarchy aspect and just consider nth-order statements that can be finitely expressed in the language of set theory involving the n-1st power set of N and lower. I would be very, very surprised if BSS machines could decide all such third-order statements but if you have a reference that implies it, I’d take a look.
Isn’t the hyperarithmetic hierarchy just contained in 1 1 statements, or equivalently 0^w statements, where you decide the truth of all first-order arithmetic statements?
I will for now retract the claim that BSS machines can decide all third order statements, mostly because I don’t have a reference to the specific fact, but I would be very surprised if BSS machines couldn’t decide all third order arithmetic statements, or any order of arithmetic that can be finitely expressed in the language of set theory, because ZFC can define a truth predicate that works for all arithmetical statements, no matter which order of arithmetic you are considering, for the reason shown below, and all finitely expressible statements in the language of arithmetic or set theory are countable, while the amount of problems they can decide and the amount of functions they can solve are uncountable, so the BSS machine is larger than any formal theory of arithmetic or set theory that is finitary.
Isn’t the hyperarithmetic hierarchy just contained in 1 1 statements, or equivalently 0^w statements, where you decide the truth of all first-order arithmetic statements?
I think you have some significant gaps in your understanding. The 0ω statements contain all first-order arithmetic statements yes. But that’s just the beginning of the hyperarithmetic hierarchy. You can then discuss sentences that have a quantifier over 0ω statements, which are 0ω+1, and iterate this to to get 02ω . Then you can iterate again. Etc. Abstracting that process gets you to 0ω2. And you keep going again and again. This is still very low in the hyperarithmetic hierarchy.
My understanding (again, this is not my area) is that given any computable ordinal (i.e. any well-ordering of the naturals that can be encoded by the outputs of some Turing machine), you can construct a corresponding level of the hyperarithmetic hierarchy. So how do you discuss an arbitrary hyperarithmetical statement? You need to be able to quantify over the Turing machines that spit out well-orderings. Verifying that an ordering is a well-ordering requires quantifying over all subsequences—a second order statement. That’s why the abstraction of the hyperarithemic hierarchy is called the first level of the analytic hierarchy, the 1 1 statements as you said.
To clarify: I agree that BSS machines can answer second order questions (maybe not the full analytic hierarchy; that’s something I’ll think more about). My confusion is about this:
where you said that it all nth-order arithmetic questions can be decided by some such machine. My above comment was why I believed that the questions that are being answered strike me as second order.
Edit for clarifying the relevance here: it strikes me as plausible that questions about BSS machines halting/not halting have inherent truth; if this would imply that third-order arithmetical questions like CH have inherent truth, I would be surprised and update my view about mathematical truth.
The reasoning is pretty similar to the second order case, and the reason here is that no matter how many orders we add to arithmetic like first-order, second-order, nth order, formal languages and theories are always constrained by the usual definition to countably infinite sets of statements and languages, and the ability to compute any function from N to N means that you have an uncountably infinite set of functions to compute, which is always larger than any individual formal languages and theories in the usual definition.
Now that the original comment has changed, I’m more unsure about what you exactly you mean. Can you be more precise about what you mean by being able to compute arbitrary nth-order arithmetical statements? Is there a BSS machine that halts if and only if CH is true? Is there a BSS machine that halts if and only if there’s a choice function on the set of non-empty subsets of R?
I admit, I haven’t found any such explicit examples yet.
I wish this was more of a common practice to give explicit examples of these mathematical statements in more computational terms.
For the Nth order arithmetical statement issue, what I’m talking about is essentially a generalization of the arithmetical hierarchy, where there’s 0 1, 0 2, 0 3 and so on defined here, until it stops at 0^w, which then continues on the analytical hierarchy from 1 1, 1 2, 1 3, until it too stops at 1^w, which can go on essentially forever.
Essentially, I’m talking about this in a generalized form:
https://en.wikipedia.org/wiki/Arithmetical_hierarchy
The formal reason why a BSS machine can compute all of this comes down, in the end to the fact that it can compute every function from the natural numbers to the natural numbers, which as a set is always larger than any arithmetical hierarchy, which means that the claim that we can always compute nth order arithmetic for any N follows easily.
So I didn’t mean to clarify what you meant by nth-order statements, but rather that BSS statements can decide them, because that seems way too strong to be true. I’m also a bit more skeptical because:
is not true; the first level of the analytic hierarchy sits on top of the hyperarithmetic hierarchy. And my understanding is that finding a way to have an analagous picture of going from something like a “hyperanalytic hierarchy” to the bottom level of third order arithmetic is something highly non-trivial/impossible/ill-defined, but this isn’t my area of math. So I think it’s easier to ignore the hierarchy aspect and just consider nth-order statements that can be finitely expressed in the language of set theory involving the n-1st power set of N and lower. I would be very, very surprised if BSS machines could decide all such third-order statements but if you have a reference that implies it, I’d take a look.
Isn’t the hyperarithmetic hierarchy just contained in 1 1 statements, or equivalently 0^w statements, where you decide the truth of all first-order arithmetic statements?
I will for now retract the claim that BSS machines can decide all third order statements, mostly because I don’t have a reference to the specific fact, but I would be very surprised if BSS machines couldn’t decide all third order arithmetic statements, or any order of arithmetic that can be finitely expressed in the language of set theory, because ZFC can define a truth predicate that works for all arithmetical statements, no matter which order of arithmetic you are considering, for the reason shown below, and all finitely expressible statements in the language of arithmetic or set theory are countable, while the amount of problems they can decide and the amount of functions they can solve are uncountable, so the BSS machine is larger than any formal theory of arithmetic or set theory that is finitary.
I think you have some significant gaps in your understanding. The 0ω statements contain all first-order arithmetic statements yes. But that’s just the beginning of the hyperarithmetic hierarchy. You can then discuss sentences that have a quantifier over 0ω statements, which are 0ω+1, and iterate this to to get 02ω . Then you can iterate again. Etc. Abstracting that process gets you to 0ω2. And you keep going again and again. This is still very low in the hyperarithmetic hierarchy.
My understanding (again, this is not my area) is that given any computable ordinal (i.e. any well-ordering of the naturals that can be encoded by the outputs of some Turing machine), you can construct a corresponding level of the hyperarithmetic hierarchy. So how do you discuss an arbitrary hyperarithmetical statement? You need to be able to quantify over the Turing machines that spit out well-orderings. Verifying that an ordering is a well-ordering requires quantifying over all subsequences—a second order statement. That’s why the abstraction of the hyperarithemic hierarchy is called the first level of the analytic hierarchy, the 1 1 statements as you said.
Alright, I’ll have to do homework today, so I can’t respond for now.