The Church-Turing-Thesis in proofs
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 :
- Run E to enumerate the next string y of L. Compare it with x.
- 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