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
=
fh
M
ij
where
M
is a TM and
L
(
M
) =
g
[10 points]
Problem 2
A
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
If
A
m
B
and
B
is a regular language, does this imply that
A
is a regular language? Why or why not? [10 points]
Problem 4
Prove that the language
LOOP
T M
=
fh
M
ij
M
is a TM and
M
loops on all inputs
g
is not recognizable. [10 points]
Problem 5
Prove that the 3-SAT problem discussed in class is an element of
NP
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]
Need assistance with this?
Solution
Welcome to brimaxessays.com