Content deleted Content added
more specific stubcat |
Conceptual error in the "enumerable language is turing recognizable" section. If the strings do not match when we enumerate, we CANNOT reject, since the string might be enumerated later on. The best we can do is continue enumerating (if the string isn't in the language it will never halt effectively rejecting). |
||
Line 25:
'''An Enumerable Language is Turing Recognizable'''
It's very easy to construct a Turing Machine <math>M</math> that recognizes the enumerable language <math>L</math>. We can have two tapes. On one tape we take the input string and on the other tape, we run the enumerator to enumerate the strings in the language one after another. Once a string is printed in the second tape we compare it with the input in the first tape. If it's a match, then we accept the input,
== References ==
| |||