The Gateway to Computer Science Excellence
0 votes
102 views

Rice theorem :

1. Any non-trivial property of the LANGUAGE recognizable by a Turing machine is undecidable.

2. Any non-monotonic property of the LANGUAGE recognizable by a Turing machine is unrecognizable

While solving please describe non-trivial/trivial and non-monotonic /monotonic property of particular statement .

Which of the following problems are undecidable?

  1. Membership problem in context-free languages.
  2. Whether a given context-free language is regular.
  3. Whether a finite state automation halts on all inputs.
  4. Membership problem for type 00 languages.
in Theory of Computation by Active (4.1k points) | 102 views

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,355 answers
198,482 comments
105,249 users