3
$\begingroup$

Currently I'm trying to understand a proof of the statement:

"A language is semi-decidable if and only if some enumerator enumerates it."

that we did in my lecture. One direction of the proof goes as follows:


Let E be an enumerator that enumerates L. We construct a TM M, that semidecides L in the following way:

Given an input string x, we design M in the following way :

  1. Run E to enumerate the next string y of L. Compare it with x.
  2. If x=y accept, else goto 1

Am I right if I say, that it is sufficient to just name an algorithm to prove the existence of such a TM M because of the Church-Turing-Thesis? Furthermore is there anything to take care of when constructing an algorithm in such a context as not to hurt the "definition" of intuitively computable?

Thanks for any answers.

$\endgroup$
2
  • 1
    $\begingroup$ The Church-Turing thesis has nothing to do with this. And, as an informal statement, it can not be used in any proof. $\endgroup$
    – Raphael
    Commented Sep 10, 2017 at 20:38
  • 1
    $\begingroup$ To construct actual Turing machines is extremely boring and unilluminating in the vast majority of cases, and so people don't do it. The moral of the story (which has not been comprehened yet, it seems) is that Turing machines are not the best way to teach computability. (Which has nothing to do with the fact that they became the historic standard for defining computability.) So, whenever you see this sort of hand-waving, yes, whoever wrote that think they could create a Turing machine, if they wanted to. $\endgroup$ Commented Sep 10, 2017 at 22:34

1 Answer 1

5
$\begingroup$

A Turing machine provides a formal definition of a "computable" function, while the Church-Turing-Thesis says that intuitive notion of "computable" coincides with the formal definition of "computable", i.e., all functions computable by TMs. This is just a hypothesis, and it is up to you to believe or not.

When we describe a procedure in order to show that some function is computable (or problem is solvable) we usually describe it at a high level, to avoid long and tedious rigorous formal details. So, you are right that "it is sufficient to just name an algorithm to prove the existence of such a TM M because of the Church-Turing-Thesis". In other words, first we informally describe a procedure using English, and then since we believe in correctness of the the Church-Turing-Thesis we conclude that the function is computable.

Another example is computing $\pi(n)-$ the $n$th digit of the decimal expansion of $\pi$. Intuitively, we can draw a circle, measure its circumference and radius, and divide the circumference by two times the radius. But this method is not suitable to implement on a computer. The Turing-Church thesis says this function is indeed computable on a Turing machine. For example, $\pi(n)$ might be computed using Taylor series.

As for the wrong usage of the thesis, usually the error may lay in a wrong assumption. For example, the following wrong procedure may seem to decide the Halting problem:

Let L be the Halting Problem language
IsHalt(W,w)
  Recursively enumerate elements of L and complement of L 
  and process one element from each set at a time
  If <W,w> is in one of them then depending in what set <W,w> is 
  return true or false

Since we loop on both $L$ and $\overline{L}$, and we enumerate each element of these sets, the procedure eventually must halt with true or false. But the wrong part is that we assumed the $\overline{L}$ is r.e.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.