4
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.