• Register
0 votes

Problem :

While doing exam revision I am having a trouble answering a following question from the book, "An Introduction to the Theory of Computation" by Sipser. Unfortunately there's no solution on this question in a book.

Explain why the below is not a legitimate Turing machine.

M = {

The input is the polynomial p over variables x1, ..., xn

  1. Try all the possible settings of x1, ..., xn to integer values
  1. Evaluate the p on all of these settings
  1. If any of these settings evaluates to 0, then accept; otherwise reject. }

How to solve this?

7 5 2
3,870 points

1 Answer

0 votes

Solution :

I think a problem is with a very last part: otherwise reject.

According to countable set basics, any vector space over the countable set is countable itself. In your case, you have the vector space over a integers of size n, which is countable. So your set of integers is also countable and therefore it is possible to try the every combination of them. (That is to say without missing any of the combination.)

Also, computing a result of p on the given set of inputs is also possible.

And entering the accepting state when p evaluates to 0 is also possible.

But, as there is an infinite number of input vectors, you can never reject a input. So no Turing machine can follow all of these rules defined in a question. Without that last rule, it is very much possible.

9 7 4
38,600 points

Related questions

1 vote
1 answer 20 views
Problem : I have created the web application and trying to host my site using the wordpress. But when I try to search the name of my site in goole it is showing me below error : A description for this result is not available because of this site's robots.txt the ... I know nothing about that error if someone could help me here Why is this happening to my site. Is there any problem in my site?
asked Dec 27, 2019 alecxe 7.5k points
0 votes
1 answer 204 views
Problem : I have recently started using Git. I am still learning about Git. I tried to do the pull from the remote repository. But now I am facing below error message: "Please enter a commit message to explain why this merge is necessary, especially if it merges an ... nothing is really happening for me. How can I fix the above error message. I am currently learning to use terminal on the OS X.
asked Mar 3 mphil 2.3k points
1 vote
1 answer 13 views
Problem : I am very new to programming. I have recently started learning C programming. Please find below the one way of initializing the array: I have one doubt about my above program : Which of the following is not a correct way to initialize an array? int n[ 5 ] = { 0, 7, 0, 3, 8, 2 }; int m[3] = ... [1] 15};     printf("m[0] = %d  m[1] = %d   m[2] = %d\n", m[0], m[1], m[2]);     return 0; }
asked Apr 27 stewart 4k points
0 votes
2 answers 24 views
Problem: Which of the following is NOT a Windows utility program? Disk Cleanup Desktop Disk Defragmenter System Restore
asked Apr 6 ArifulIslam 5.7k points