5
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ A question by Dmytro Taranovsky might be relevant. (Unfortunately, it does not receive any answer.) $\endgroup$
    – Hanul Jeon
    Commented Feb 1, 2021 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 ♦
    Commented Feb 1, 2021 at 12:28

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .