Theory Of computation’s question

Project Description:

A few questions on reduction and turing machine like to use the reduction to show some language is undecidable.

Problem 1

Use a reduction to show that the language

ALL

T M

is undecidable

ALL

T M

where

is a TM and

(

) =

[10 points]

Problem 2

useless state

in a Turing machine is one that is never entered

on any input string. Consider the problem of determining whether a Turing

Machine has any useless states. Formulate this problem as a language and show

that it is undecidable. [10 points]

Problem 3

and

is a regular language, does this imply that

is a regular language? Why or why not? [10 points]

Problem 4

Prove that the language

LOOP

T M

is a TM and

loops on all inputs

is not recognizable. [10 points]

Problem 5

Prove that the 3-SAT problem discussed in class is an element of

by giving a veri er and a NTM decider that run in poly-time. (Only one

of these is required for a proof, but I’d like both for this question.) [10 points]