Content deleted Content added
I've added the equivalence of enumerable languages and Turing Recognizable Languages. |
|||
Line 14:
==Equivalence of Enumerator and Turing Machines==
A language over a finite alphabet is Turing Recognizable if and only if it can be enumerated by an enumerator. This shows Turing recognizable languages are also recursively enumerable.
{{cite book |last=Sipser |first=Michael |title=Introduction to the Theory of Computation - International Edition |year=2012 |isbn=978-1-133-18781-3}}▼
'''Proof'''
'''A Turing Recognizable language can be Enumerated by an Enumerator'''
Consider a Turing Machine <math>M</math> and the language accepted by it be <math>L(M)</math>. Since the set of all possible strings over the input alphabet <math>\Sigma</math> i.e. the Kleene Closure <math>\Sigma^{*}</math> is a countable set, we can enumerate the strings in it as <math>s_{1},s_{2},\dots ,s_{i},</math> etc. Then the Enumerator enumerating the language <math>L(M)</math> will follow the steps:
1 '''for''' i = 1,2,3,...
2 '''Run''' <math>M</math> '''with input strings''' <math>s_{1}, s_{2}, \dots, s_{i}</math> '''for''' <math>i</math>-'''steps'''
3 If any string is accepted, then print it.
Now the question comes whether every string in the language <math>L(M)</math> will be printed by the Enumerator we constructed. For any string <math>w</math> in the language <math>L(M)</math> the TM <math>M</math> will run finite number of steps(let it be <math>k</math> for <math>w</math>) to accept it. Then in the <math>k</math>-th step of the Enumerator <math>w</math> will be printed. Thus the Enumerator will print every string <math>M</math> recognizes but a single string may be printed several times.
'''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 its a match, then we accept the input, else reject.
== References ==
▲{{cite book |last=Sipser |first=Michael |title=Introduction to the Theory of Computation - International Edition |year=2012 |isbn=978-1-133-18781-3}}
[[Category: Computability theory]]
[[Category: Theory of computation]]
| |||