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?

Related posts

October 25, 2020

Organizations develop numerous teams as part of their operational environment. These teams perform different activities, such as decision-making, advi

---

Read more

+1 (786) 788-0496

Welcome to brimaxessays.com

Hello 👋
We will write your work from scratch and ensure it's plagiarism-free, you just submit the completed work.