0
$\begingroup$

Hartley Rogers Jr., on pg. 120 of his text, Theory of Recursive Functions and Effective Computability, presents and discusses the following characterization of the sets in $\mathscr P(\omega)$:

$\mathscr B_{0}$ = {$A$| $A$ is recursively enumerable}

$\mathscr B_{1}$ = {$A$| $A$ is immune}

$\mathscr B_{2}$ = {$A$| $A$ is not recursively enumerable and $A$ is the union of an infinite recursively enumerable set and an immune set}

$\mathscr B_{3}$ = {$A$| ($\forall $recursively enumerable $B$) [$B$ $\subset$ $A$ $\Rightarrow$ ($\exists$ recursively enumerable $C$) [$C$ $\subset$ $A$ & $C$ infinite & $C$ $\cap$ $B$ = $\emptyset$]] where no uniform effective method exists for finding an r.e. index for such a $C$ from an r.e. index for $B$}

$\mathscr B_{4}$ = {$A$| $A$ is productive}

then states

It is trivial to show (Exercise 8-34) that this classification is mutually exclusive and exhaustive [for $\mathscr P$($\omega$)--my comment]. Classes $\mathscr B_{1}$ to $\mathscr B_{4}$ may be viewed as regions along a spectrum of increasing "richness" in the possession of recursively enumerable subsets.

Can this "mutually exclusive and exhaustive" classification of the members of $\mathscr P$($\omega$) be shown to fail if one replaces the notion of "Turing machine" implicit in the definition of this classification with "ITTM", and if this classification does, in fact, hold for ITTM's, in which of these classes can one find "lost melodies"?

Improve this question
$\endgroup$
32
  • $\begingroup$ Are you certain you've transcribed this correctly? As written, I'm fairly sure a 1-generic falls into both $B_1$ and $B_3$. $\endgroup$
    – Dan Turetsky
    Commented Aug 13, 2021 at 6:33
  • $\begingroup$ Perhaps it's supposed to be $C\cap B =^* \emptyset$? $\endgroup$
    – Dan Turetsky
    Commented Aug 13, 2021 at 6:45
  • $\begingroup$ @DanTuretsky: Thanks. Fixed. $\endgroup$
    – Thomas Benjamin
    Commented Aug 13, 2021 at 7:43
  • $\begingroup$ @DanTuretsky: Did adding $C$ $\subset$ $A$ to $\mathscr B_{3}$ fix the problem? That would have been the correct transcription so I just wanted to check. $\endgroup$
    – Thomas Benjamin
    Commented Aug 13, 2021 at 20:38
  • $\begingroup$ @ThomasBenjamin Some thoughts about $\mathscr B_{0}$. One question is that, for this question, how would one define the analogue of r.e. or c.e. sets in the case of ITTMs. For example, one definition of c.e. set is that for any such set $A$ we must be able to find a program computing a partial computable function $f:\mathbb{N} \rightarrow \mathbb{N}$ such that the function $f$ halts precisely on those inputs $a$ for which $a \in A$. And for the other inputs $a$ where $a \notin A$, the program computing $f$ never halts. $\endgroup$
    – SSequence
    Commented Aug 15, 2021 at 18:03

0

Reset to default

You must log in to answer this question.