Register

Peter Linz Edition 5 Exercise 12.1 Question 7,8 (Page No. 308)

• retagged by
156 views

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

0 votes
0 votes
0 answers
1
Rishi yadav asked Mar 14, 2019
190 views
Peter Linz Edition 5 Exercise 12.1 Question 16 (Page No. 308)
Determine whether or not the following statements is true: Any problem whose domain is finite is decidable.
Determine whether or not the following statements is true: Any problem whose domain is finite is decidable.
User Avatar
0 votes
0 votes
0 answers
2
Rishi yadav asked Mar 14, 2019
143 views
Peter Linz Edition 5 Exercise 12.1 Question 15 (Page No. 308)
Let $\Gamma = \{0,1,\square\}$ and let $b(n)$ be the maximum number of tape cells examined by any $n-$state Turing machine that halts when started with a blank tape. Show that $b(n)$ is not computable.
Let $\Gamma = \{0,1,\square\}$ and let $b(n)$ be the maximum number of tape cells examined by any $n-$state Turing machine that halts when started with a blank tape. Show...
User Avatar
0 votes
0 votes
0 answers
3
Rishi yadav asked Mar 14, 2019
153 views
Peter Linz Edition 5 Exercise 12.1 Question 14 (Page No. 308)
Consider the set of all $n-$state Turing machines with tape alphabet $\Gamma = \{0,1,\square\}$. Give an expression for $m(n)$, the number of distinct Turing machines with this $\Gamma$.
Consider the set of all $n-$state Turing machines with tape alphabet $\Gamma = \{0,1,\square\}$. Give an expression for $m(n)$, the number of distinct Turing machines wit...
User Avatar
1 votes
1 votes
1 answer
4
Rishi yadav asked Mar 14, 2019
363 views
Peter Linz Edition 5 Exercise 12.1 Question 13 (Page No. 308)
Let $B$ be the set of all Turing machines that halt when started with a blank tape. Show that this set is recursively enumerable, but not recursive.
Let $B$ be the set of all Turing machines that halt when started with a blank tape. Show that this set is recursively enumerable, but not recursive.
User Avatar
Link Copied!