Register

Ullman (TOC) Edition 3 Exercise 9.3 Question 8 (Page No. 401)

• edited by
262 views
0 votes
0 votes

Tell whether each of the following are recursive, RE-but-not-recursive, or non-RE.

  1. The set of all $TM$ codes for $TM's$ that halt on every input.
  2. The set of all $TM$ codes for $TM’s$ that halt on no input.
  3. The set of all $TM$ codes for $TM's$ that halt on at least one input.
  4. The set of all $TM$ codes for $TM's$ that fail to halt on at least one input.  
• edited by
User Avatar

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

274
views
0 answers
0 votes
admin asked Jul 21, 2019
274 views
Ullman (TOC) Edition 3 Exercise 9.3 Question 7 (Page No. 400 - 401)
Show that the following problems are not recursively enumerable:The set of pairs $(M,w)$ such that $TM \ M$, started with input $w$, does not halt.The set ... language of the first is the concatenation of the languages of the two $TM's$.
User Avatar
191
views
0 answers
0 votes
admin asked Jul 21, 2019
191 views
Ullman (TOC) Edition 3 Exercise 9.3 Question 5 (Page No. 400)
Let $L$ be the language consisting of pairs of $TM$ codes plus an integer, $(M_{1},M_{2},k)$, such that $L(M_{1})\cap L(M_{2})$ contains at least $k$ strings. Show that $L$ is $RE$, but recursive.
User Avatar
664
views
1 answers
0 votes
admin asked Jul 21, 2019
664 views
Ullman (TOC) Edition 3 Exercise 9.2 Question 3 (Page No. 391)
Informally describe multitape Turing machines that enumerate the following sets of integers, in the sense that started with blank tapes, it prints on one of its tapes ... discover each $M_{i}$ that accepts $w_{i}$ and enumerate $i$.
User Avatar
198
views
0 answers
0 votes
admin asked Jul 21, 2019
198 views
Ullman (TOC) Edition 3 Exercise 8.4 Question 9 (Page No. 352)
A $k$-head Turing machine has $k$ heads reading cells of one tape. A move of this $TM$ depends on the state and on the symbol scanned by each head. In one ... by $k$-head Turing machines are the same as those accepted by ordinary $TM's$.
User Avatar
Link Copied!