patternMinor
Are there any more complex problems than the Totality Problem that appear in the practical world?
Viewed 0 times
totalityproblemtheareanymorethanproblemsworldthat
Problem
We know the Halting Problem is in the 1st level of arithmetical hierarchy. We know that the Totality Problem is in the 2nd level of arithmetical hierarchy. What are some examples of problems in the 3rd (or higher) level of arithmetical hierarchy. +1 for problems which instances are solved in the practical world (programmers, mathematicians, etc.).
Solution
Let $\{W_e\}_{e\in\mathbb N}$ be a canonical list of the recursively enumerable, i.e., computably enumerable, i.e., Turing recognizable, languages (or sets).
The property that $W_e$ is actually recursive, i.e., computable, is $\Sigma^0_3$:
$$\exists d\forall n(n\in W_e\leftrightarrow n\not\in W_d).$$
It is at the 3rd level of the hierarchy: it is not of lower complexity than $\Sigma^0_3$. See e.g. Soare: Recursively enumerable sets and degrees, Theorem 3.4, for the proof.
The property that $W_e$ is actually recursive, i.e., computable, is $\Sigma^0_3$:
$$\exists d\forall n(n\in W_e\leftrightarrow n\not\in W_d).$$
It is at the 3rd level of the hierarchy: it is not of lower complexity than $\Sigma^0_3$. See e.g. Soare: Recursively enumerable sets and degrees, Theorem 3.4, for the proof.
Context
StackExchange Computer Science Q#77642, answer score: 4
Revisions (0)
No revisions yet.