In descriptive complexity, HO corresponds to ELEMENTARY.

ELEMENTARY is a subset of R, so therefore all HO queries are decidable.

Then undecidable problems have no corresponding HO query. Is my understanding correct? If so, can I have an example undecidable problem and an intuitive/informal explanation of why it doesn't have a corresponding HO query?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.