# Explain why the following is not a description of a legitimate turing machine

272 views

## 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?

## 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.

## Related questions

1 vote
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?
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.
22 views
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!
1 vote
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; }
51 views
Problem: Which of the following is NOT a Windows utility program? Disk Cleanup Desktop Disk Defragmenter System Restore
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.