• 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

0 votes
1 answer 2 views
Problem: The task is to construct a DFA for this language over the alphabet {0,1}. Why should my DFA accept an empty word if in the empty word there is no 1 at the odd position which means that it is not in the language?
asked 3 days ago ummesalma 25.2k points
0 votes
1 answer 271 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
1 vote
1 answer 24 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 68 views
Problem: I am unable to understand that why java is platform independent. Please explain it with example.
asked Nov 4, 2020 Mubashi-Question 1.7k points
0 votes
1 answer 15 views
Problem: I have a select control, and in a javascript variable I have a string. Using jquery I need to set the chose thing of the select control to be the thing with the portrayal text that I have (instead of the worth, which I don't have). I realize ... content description. I surmise there should be an approach to get the incentive from the content portrayal, yet I am desperate to sort it out.
asked Feb 15 sasha 16.2k points
0 votes
1 answer 16 views
16 views asked Aug 7, 2020 game 4.6k points
0 votes
1 answer 3 views
Problem: I tried to find out the solution on the web when I face this problem but I did not get any fruitful information that I can continue if you read the above question and understand what is the solution of this please cooperate with me- Thanks
asked Mar 23 rubelkhan 20.4k points