This is a somewhat open-ended question, so let me motivate it a little.

One of the first results in the study of Ordinal Turing Machines includes the following computational characterization of $L$ by Koepke:

Theorem. a set of ordinals is in $L$ if and only if it is computable by an Ordinal Turing Machine with finitely many parameters.

At the same time, $\mathsf{HOD}$ has a "definable power set" characterization: in the construction on $L$, if we replace the first-order definable power set operator with second-order definable power set, then the resulting structure is $\mathsf{HOD}$. This is proved by Myhill and Scott, and is also nicely written up in this MO post.

So a natural question is this: can there be a computational notion $C$ such that something analogous to Koepke's theorem is provable for $\mathsf{HOD}$? By this I have in mind something to the effect of "a set (of ordinals) is in $\mathsf{HOD}$ if and only if it is $C$-computable."

A somewhat trivial candidate would be just oracle-OTM computation. This uses the observation that $\mathsf{HOD}$ is always coextensive with $L[A]$ for some class of ordinals $A$, and we can just relativize Koepke's theorem to $A$. But can we do more?

  • 1
    $\begingroup$ A question by Dmytro Taranovsky might be relevant. (Unfortunately, it does not receive any answer.) $\endgroup$ – Hanul Jeon Feb 1 at 9:41
  • 2
    $\begingroup$ At some point you gotta ask yourself what counts as a computation. If you need a 2nd-order oracle mechanism, then is it really a computation? $\endgroup$ – Asaf Karagila Feb 1 at 12:28

If you consider recognizability instead of computability, you get as far up as an inner model for a Woodin cardinal, see "Recognizable Sets and Woodin Cardinals: Computations Beyond the Constructible Universe". Of course, this is still far below HOD in general.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.