RECALL: Turing recognizable Turing acceptable recunsively enumerable (depends on
ID: 3901524 • Letter: R
Question
RECALL: Turing recognizable Turing acceptable recunsively enumerable (depends on author) decidable recursive 1. (25) Answer the following briefly but completely. a. Who is this man and why is he important to computer science? Hint b. Now that you have proved that ATM is undecidable, what is the usual way to prove that FINITE («M> L(M) ?s finite) is undecidable? c. Define the problem HALTTM reaa o d. If A reduces to B and B is decidable, what can we say aboutA? e. If A reduces to B and A is decidable, what can we say about B?Explanation / Answer
a. Noam Chomsky is the man in given photo. His contribution to computer science. especially in field of automata is immensely great. He has given a hierarchy on the basis of which we are capable to differentiate grammars and languages and their powers. This helped us to set formal languages that are helpful for building automata, turing machine, compilers, etc in field of computer science.
b. Let R be a TM that decides FINITE(TM) and now we'll construct a TM S to decide A(TM), but A(TM) is given to be undecidable and we will give the desired contradiction that FINITE(TM) is undecidable.
S is a TM such that on input <M,w> where M is a TM and w is any string:
constructing a TM 'M2' that on input x does following:
Run M2 on w. If M accepts w, accept. Otherwise, reject.
Run R on M2:
If R accepts, then reject. Otherwise accept.
c. It is a problem of determining whether the Turing Machine, on basis of a description given by any arbitary program, will finish computing a string w in a finite number of steps or not.
d. If A reduces to B and B is decidable, then A is also DECIDABLE.
e. If A reduces to B and A is decidable, nothing can be claimed about B.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.