# Prove projection of a computable function is computable without using Church-Turing Thesis

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.

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$$.
• 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$.
• @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. Commented Jun 2, 2023 at 16:51
• 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.
• @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. Commented Jun 4, 2023 at 15:51