patternMinor
Kleene's Theorem and TMs
Viewed 0 times
andtmskleenetheorem
Problem
I wanted to know that based on Kleene's theorem (a language is regular iff some FSA recognizes it), does every regex have a TM (Turing machine) that halts on exactly the same language?
Is this implication valid or are we not entirely sure about this? (ambiguous/unclear given the theorem). Kind of like the Church-Turing thesis about computation in the future and all computation in general.
Is this implication valid or are we not entirely sure about this? (ambiguous/unclear given the theorem). Kind of like the Church-Turing thesis about computation in the future and all computation in general.
Solution
We can prove the following theorem:
Theorem: A language $L$ is regular if and only if there exists a DFA or NFA for language $L$.
Turing machines are more powerful than DFAs and NFAs. In particular, every finite state automaton can be simulated by some Turing machine.
So, according to the above propositions, the answer to your question is yes: every regex has a Turing machine whose language is identical.
Theorem: A language $L$ is regular if and only if there exists a DFA or NFA for language $L$.
Turing machines are more powerful than DFAs and NFAs. In particular, every finite state automaton can be simulated by some Turing machine.
So, according to the above propositions, the answer to your question is yes: every regex has a Turing machine whose language is identical.
Context
StackExchange Computer Science Q#132814, answer score: 5
Revisions (0)
No revisions yet.