• 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

Please log in or register to answer this question.

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 22 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 235 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, 2020 mphil 2.3k points
0 votes
1 answer 6 views
Problem: Which of the following is not a comparison operator? >= == != || I do not know a lot about these operators. Please tell me the correct choice and explain all the above-mentioned operators and their functionality. Thanks!
asked 1 day ago Code Learner 5.5k points
1 vote
1 answer 31 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, 2020 stewart 4k points
0 votes
2 answers 51 views
Problem: Which of the following is NOT a Windows utility program? Disk Cleanup Desktop Disk Defragmenter System Restore
asked Apr 6, 2020 ArifulIslam 5.6k points
0 votes
1 answer 27 views
Problem: Which of the following is NOT a rule that must be followed when naming identifiers? A. Identifiers for constants should use an underscore between words. B. Identifiers should use periods to separate words. C. Identifiers should list the data type at the end of the name. D. Identifiers can contain spaces.
asked Mar 9, 2020 ArifulIslam 5.6k points
0 votes
2 answers 143 views
Problem: Which of the following is not a valid C++ identifier?
asked Mar 9, 2020 ArifulIslam 5.6k points
0 votes
1 answer 101 views
Problem: I am new, I need help, can anyone help me? Which of the following is not a task handled by a router? A router can connect dissimilar networks. A router can reroute traffic if the path of first choice is down but a second path is available. A router forwards broadcasts over the network. A router can interpret Layer 3 and often Layer 4 addressing.
asked Feb 23, 2020 maddi86 5.4k points
0 votes
1 answer 29 views
Solution: Can anyone help it was actually asked in exam as following: Which of the following options is not a likely source of electromagnetic interference? A) power lines B) motors C) fiber optic cables D) microwaves
asked Feb 18, 2020 maddi86 5.4k points