Register

Peter Linz Edition 5 Exercise 11.1 Question 15 (Page No. 284)

328 views
0 votes
0 votes
$\text{Theorem}:$ There exists a recursively enumerable language whose complement is not recursively enumerable.

Choose a particular encoding for Turing machines, and with it, find one element of the languages $\bar{L}$ in Theorem
User Avatar

1 Answer

1 votes
1 votes

  • Recursive ennum is not closed under complement

  • L= {< M>/ TM  'M'  halts on string s } 

  • Here L is recursive ennum. But complement of L is not recursive ennum .
• edited by
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
0 answers
2
Rishi yadav asked Mar 16, 2019
204 views
Peter Linz Edition 5 Exercise 11.1 Question 18 (Page No. 284)
$\text{Theorem}:$ Let $S$ be an infinite countable set. Then its powerset $2^S$ is not countable. Why does the argument in Theorem fail when $S$ is finite$?$
$\text{Theorem}:$ Let $S$ be an infinite countable set. Then its powerset $2^S$ is not countable.Why does the argument in Theorem fail when $S$ is finite$?$
User Avatar
0 votes
0 votes
1 answer
4
Rishi yadav asked Mar 16, 2019
321 views
Peter Linz Edition 5 Exercise 11.1 Question 16 (Page No. 284)
Let $S_1$ be a countable set, $S_2$ a set that is not countable, and $S_1 \subset S_2$. Show that $S_2$ must then contain an infinite number of elements that are not in $S_1$.
Let $S_1$ be a countable set, $S_2$ a set that is not countable, and $S_1 \subset S_2$. Show that $S_2$ must then contain an infinite number of elements that are not in $...
User Avatar
Link Copied!