Register

Peter Linz Edition 5 Exercise 12.1 Question 6 (Page No. 308)

• retagged by
472 views
0 votes
0 votes
Consider the question: $“$Does a Turing machine in the course of a computation revisit the starting cell $($i.e the cell under the read-write head at the beginning of the computation$)?$$”$ Is this a decidable question$?$
• retagged by
User Avatar

1 Answer

0 votes
0 votes
Undecidable as standard state entry problem for TM is undecidable.
User Avatar
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
147 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!