State and prove Rice's theorem.

1.6kviews

written 5.6 years ago by

teamques10 ★ 65k

Theorem

L = {<m> | L (M) ∈ P} is undecidable when p, a non-trivial property of the Turing machine, is undecidable.

If the following two properties hold, it is proved as undecidable −

Property 1 − If M1 and M2 recognize the same language, then either <m1> <m2> ∈ …

Create a free account to keep reading this post.

and 5 others joined a min ago.

ADD COMMENT EDIT