Let $R(x,y)$ be a computable relation. I want to prove that for any fixed $y$, the set $S_y$ defined by $S_y := \{ \; x\; | \; R(x,y) \; \}$ is computable. I know this can be reasoned with the Church-Turing Thesis, that is take a total TM $M$ which computes $R$ and create another TM with $y$ hardwired that then simulates $M(x,y)$. However, I was wondering if a more formal proof is possible.


1 Answer 1


This is fairly trivial. For a fixed $y$, we can clearly produce a Turing machine $T_1$ which, given an input of $x$, will write out $x, y$ on the tape. Because $R$ is decidable, there is a Turing machine $T_2$ which, given $x, y$ on the tape, decides whether $R(x, y)$. Then $T_2 \circ T_1$ will, given $x$, decide whether $x \in S_y$.

I do not understand how the Church-Turing thesis, which is a non-mathematical claim, is relevant here. All that is required is a straightforward application of the definition of “computable”, a term which is mathematically well-defined.

  • $\begingroup$ However, this depends on the machine $T_1$ having ""knowledge" of $y$ built into it. I'm wondering if there is a way to establish that $S_y$ can be computed independent of such a construction, that is independent of composition with $T_2$. $\endgroup$
    – Ari
    Jun 1 at 22:38
  • $\begingroup$ @Ari I do not understand your comment. Obviously, our Turing machine will need to have knowledge of $y$, since $S_y$ depends on $y$. Furthermore, your second sentence indicates you have an issue with $T_2$, but this is the part of the construction which does not require knowledge of $y$. I’m unsure what it would mean for the computation to be “independent” of another computation. $\endgroup$ Jun 2 at 16:51
  • $\begingroup$ My point was this: I totally agree with you. I'm just interested in if there is another proof that does not use simulation to show that derived language $S_y$ is computable for any $y$. An analogy for what I am after is like finding a proof that non-computable sets exist through a method that does not rely on the diagonal argument of the Halting Problem. And there is one in that case: A counting argument (countably many Turing Machine programs vs. uncountably many subsets of $\mathbb{N}$). The diagonal proof gives more insight but the counting argument is still good enough in this case. $\endgroup$
    – Ari
    Jun 4 at 2:51
  • $\begingroup$ @Ari Your example doesn’t make much sense to me, since the proof that $2^\mathbb{N}$ is uncountable is itself a diagonal argument. You’re just pushing back the diagonalization one step. $\endgroup$ Jun 4 at 15:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .