Return to Question

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"?

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"?

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"?

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"?

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$ 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"?

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"?