3
$\begingroup$

(By "stream" I mean "a sequence that might be finite.")

Given a Turing machine $T$ and a natural number $n$, write $T_n$ for the stream of $0$'s and $1$'s that appears in the first position of the tape given that the tape starts off with a description of $n$ written on it.

If I understand correctly:

  • A set $X \subseteq \mathbb{N}$ is said to be computable iff there exists a Turing machine $T$ such that for all $n \in \mathbb{N}$, we have that $T_n$ is a finite stream, and the last item in this stream is a $1$ if $n \in X$, and it's a zero otherwise.

  • As set $X \subseteq \mathbb{N}$ is said to be computably enumerable iff there exists a Turing machine $T$ such that for all $n \in \mathbb{N}$, if $n \in X$ then $T_n$ is a finite stream, and if $n \notin X$ then $T_n$ is an infinite stream.

I'm interested in a generalization of these notions. Define $X \subseteq \mathbb{N}$ to be weakly computable iff there exists a Turing machine $T$ such that for all $n \in \mathbb{N}$, if $n \in X$ then $T_n$ is eventually equal to $1$, and if $n \in X$, then $T_n$ is eventually equal to $0$.

Subquestion. Do these sets have an accepted name?

So basically, we remove all halting requirements, so that at not point do we know whether or not the $0$ or $1$ we've computed is actually correct. But we require that eventually it's correct, even if we don't know whether or not the value we're currently looking at is this eventual stable value.

It's clear that every computably ennumerable set is also weakly computable; just put a $0$ in the first position early on, and change it to a $1$ if you need to. Also, by symmetry, the weakly computable sets are closed under complementation.

Question. I guess it's possible that the "weakly computable" sets are precisely those that are arithmetical. Is this correct, and if not, is there a nice description of them via universal and existential quantifiers over $\mathbb{N}$ nonetheless?

$\endgroup$
2
$\begingroup$

These sets are usually called $\mathit{limit\ computable}$, and they have two important characterizations. 1) They are exactly the sets oracle-computable from the Halting problem; and 2) They are exactly the sets at level $\Delta_2$ of the arithmetical hierarchy, i.e., exactly those $X$ which can both be expressed $x \in X \leftrightarrow \exists y \forall z( \psi(x,y,z))$ and be expressed $x \in X \leftrightarrow \forall y\exists z( \theta(x,y,z))$ where $\psi$ and $\theta$ do not have unbounded quantifiers.

In particular, the limit computable sets make up only a small part of the arithmetical sets. However, if you define a broader class of sets of all $\mathit{limits\ of\ limit}$-$\mathit{computable}\ T_n$, where the sequence of machines $T_n$ is itself chosen by a Turing machine, this turns out to be the class of $\Delta_3$ sets. And as you might guess, if you keep going, all arithmetical sets can be written this way, as limits of limits of limits$\ldots$of limits.

$\endgroup$

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.