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.
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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$– AriJun 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$– AriJun 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