Question

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.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top