Skip to main content

Let $K$ denote the set of halting Turing machines (TMs). You are asking (1) for what kind of sets $A$ of TMs is $A \cap K$ decidable, and (2) is there a maximal such $A$. Question 2 has been answered in the comments, I think, but to go over it again: Since $F \cap K$ is decidable for every finite $F$, any maximal such $A$ must have $A \cap K = K$, which cannot be, because $K$ is not decidable.

Question 1 can be rephrased a little more simply as: What kind of subsets $A \subseteq K$ are decidable? There are lots of such $A$, to wit: TMs that execute a primitive recursive procedure, TMs that execute as a finite automaton, TMs $M$ that halt after fewer than $f(M)$-many steps, where $f$ is a computable function that takes $M$'s program as input.

Here's a funny fact I noticed. If $f$ is a computable function, let $K_f = \{M : M\ \mathrm{halts\ in\ fewer\ than}\ f(M)\ \mathrm{steps}\}$. Clearly any such $K_f$ is a computable set; the funny fact is that if $A \subseteq K$ is computable, then $A \subseteq K_f$ for some $f$. (You can use $A$ to construct an appropriate $f$.) So to specify an infinite computable subset of $K$ is more-or-less the same as first selecting ana maximum runtime $f$, then selecting any computable subset of the computable set $K_f$.

Let $K$ denote the set of halting Turing machines (TMs). You are asking (1) for what kind of sets $A$ of TMs is $A \cap K$ decidable, and (2) is there a maximal such $A$. Question 2 has been answered in the comments, I think, but to go over it again: Since $F \cap K$ is decidable for every finite $F$, any maximal such $A$ must have $A \cap K = K$, which cannot be, because $K$ is not decidable.

Question 1 can be rephrased a little more simply as: What kind of subsets $A \subseteq K$ are decidable? There are lots of such $A$, to wit: TMs that execute a primitive recursive procedure, TMs that execute as a finite automaton, TMs $M$ that halt after fewer than $f(M)$-many steps, where $f$ is a computable function that takes $M$'s program as input.

Here's a funny fact I noticed. If $f$ is a computable function, let $K_f = \{M : M\ \mathrm{halts\ in\ fewer\ than}\ f(M)\ \mathrm{steps}\}$. Clearly any such $K_f$ is a computable set; the funny fact is that if $A \subseteq K$ is computable, then $A \subseteq K_f$ for some $f$. (You can use $A$ to construct an appropriate $f$.) So to specify an infinite computable subset of $K$ is more-or-less the same as first selecting an $f$, then selecting any computable subset of the computable set $K_f$.

Let $K$ denote the set of halting Turing machines (TMs). You are asking (1) for what kind of sets $A$ of TMs is $A \cap K$ decidable, and (2) is there a maximal such $A$. Question 2 has been answered in the comments, I think, but to go over it again: Since $F \cap K$ is decidable for every finite $F$, any maximal such $A$ must have $A \cap K = K$, which cannot be, because $K$ is not decidable.

Question 1 can be rephrased a little more simply as: What kind of subsets $A \subseteq K$ are decidable? There are lots of such $A$, to wit: TMs that execute a primitive recursive procedure, TMs that execute as a finite automaton, TMs $M$ that halt after fewer than $f(M)$-many steps, where $f$ is a computable function that takes $M$'s program as input.

Here's a funny fact I noticed. If $f$ is a computable function, let $K_f = \{M : M\ \mathrm{halts\ in\ fewer\ than}\ f(M)\ \mathrm{steps}\}$. Clearly any such $K_f$ is a computable set; the funny fact is that if $A \subseteq K$ is computable, then $A \subseteq K_f$ for some $f$. (You can use $A$ to construct an appropriate $f$.) So to specify an infinite computable subset of $K$ is more-or-less the same as first selecting a maximum runtime $f$, then selecting any computable subset of the computable set $K_f$.

Source Link

Let $K$ denote the set of halting Turing machines (TMs). You are asking (1) for what kind of sets $A$ of TMs is $A \cap K$ decidable, and (2) is there a maximal such $A$. Question 2 has been answered in the comments, I think, but to go over it again: Since $F \cap K$ is decidable for every finite $F$, any maximal such $A$ must have $A \cap K = K$, which cannot be, because $K$ is not decidable.

Question 1 can be rephrased a little more simply as: What kind of subsets $A \subseteq K$ are decidable? There are lots of such $A$, to wit: TMs that execute a primitive recursive procedure, TMs that execute as a finite automaton, TMs $M$ that halt after fewer than $f(M)$-many steps, where $f$ is a computable function that takes $M$'s program as input.

Here's a funny fact I noticed. If $f$ is a computable function, let $K_f = \{M : M\ \mathrm{halts\ in\ fewer\ than}\ f(M)\ \mathrm{steps}\}$. Clearly any such $K_f$ is a computable set; the funny fact is that if $A \subseteq K$ is computable, then $A \subseteq K_f$ for some $f$. (You can use $A$ to construct an appropriate $f$.) So to specify an infinite computable subset of $K$ is more-or-less the same as first selecting an $f$, then selecting any computable subset of the computable set $K_f$.