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

434 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

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?
24 views
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.
1 vote
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?
68 views
Problem: I am unable to understand that why java is platform independent. Please explain it with example.
15 views