Determine if the machine can accept infinitely

Assignment Help Theory of Computation

Reference no: EM133033659

Theory of Computation Assignment

Question 1. Consider the following language

INF_TM = {(M)|L(M ) is finite}

We are given a TM description as input, and we want to determine if the machine can accept infinitely many strings. Prove that INFTM is undecidable. (Hint: reduce from A_TM)

Question 2. Consider the following language.

DIS_TM = {(M₁, M₂)|L(M₁) ∩ L(M₂) = ∅}}

We are given two machines, and we want to check if the machines are disjoint - that is, they don't recognize any of the same strings.

Prove that DISTM is undecidable. (Hint: reduce from ETM. Use the fact that is the only language that is disjoint from Σ∗.)

Question 3. Consider the following language

L = {(M, D)|M is a TM, D is a DFA, L(M ) = L(D)}

We are given a TM description and a DFA description, and we want to determine if the two machines are equivalent. Note that this is different from EQ_TM because one of the input machines is a DFA. Prove that L is undecidable. (Hint: reduce from ALL_TM).

Question 4. This problem is taken from problem 5.22 in Sipser. Prove that a language L is Turing- recognizable if and only if L ≤_m A_TM. For full credit make sure your proof includes both directions.

Question 5.(a) Prove that if L ≤_m L¯ then L¯ ≤_m L

(b) Prove that L is Turing-recognizable and L ≤_m L¯ then L is decidable.

Reference no: EM133033659

Questions Cloud

Define inflection point : Define "inflection point". Think about a behavior you are trying to change (for example, checking your email less frequently, reducing the number of cigarettes

What are the gains and losses of globalization : Question 1: To summarize, is globalization inevitable? Provide references.

Explain the meaning of contract of sale : Explain the meaning of "contract of sale". Describe the various classifications of agents.

Identify the change strategy being implemented : Bounce Fitness is adapting a new application for its Point of Sales system. It's a new application developed to ensure smoother transaction using a cloud system

Determine if the machine can accept infinitely : Determine if the machine can accept infinitely many strings. Prove that INFTM is undecidable. (Hint: reduce from ATM)

Identify five significant underwriting considerations : You are a property underwriter for an insurer that specialises in UK-based household insurance. As part of the insurer's growth strategy, it has decided to expa

Value of irrational strategic management : With the development of economy, original pure rational strategic management could not adapt to the complex and ever-changing environment now.

What is a maturity bucket in the repricing model : Question - What is a maturity bucket in the repricing model? How does this impact runoff

University of newcastle marketing services : The University of Newcastle marketing services are interested in mobile usage technology. A study was undertaken in which a random sample of students enrolled a

User Account

All Pages