Are there any problems outside of the arithmatical hierarchy?

162 Views Asked by At

Do there exist problems that are outside of any level of the arithmetical hierarchy(as in even outside arbitrarily large ordinal levels?) But are in ALL. In other words, does AH = ALL?(where AH is all of the levels of the arithmetical hierarchy, including all ordinals). If these problems do exist, what are some examples? If there are not problems like this, what is the highest level of the arithmetical hierarchy(the level that is equivalent to ALL) Another way to ask this would be "are there any problems that cannot be computed by a Turing machine with access to a halting oracle for an arbitrary level of AH?"

1

There are 1 best solutions below

6
On

Arithmetical hierarchy can be extended to infinite coutable ordinals up to a point : at least you need the ordinal to be computable, otherwise, you can't define a way for the turing machine to effectively ask a question to the oracle. So you are limited to be under $\omega_1^{CK}$

I don't think it means anything to define the AH for all ordinals (definition problem). So AH up to its limit will only contains a countable number of problems, but the cardinal of all decision problems is $2^{\aleph_0}$