L = { <M,t> : t ∈ L(M) and s ∉ L(M), t,s ∈ {a,b}, where t is the string after s in a lexicographic ordering of {a,b}}.

Chapter21RicesTheoremandBeyondFile.ppt

Home >Computer Science homework help >L = { <M,t> : t ∈ L(M) and s ∉ L(M), t,s ∈ {a,b}*, where t is the string after s in a lexicographic ordering of {a,b}*}.

Decidability and Undecidability Proofs

Sections 21.4 - 21.7

Is There a Pattern?

● Does L contain some particular string w?

● Does L contain ?

● Does L contain any strings at all?

● Does L contain all strings over some alphabet ?

● A = {<M, w> : TM M accepts w}.

● A = {<M> : TM M accepts }.

● AANY = {<M> : there exists at least one string that

TM M accepts}.

● AALL = {<M> : TM M accepts all inputs}.

Rice’s Theorem

No nontrivial property of the SD languages is decidable.

Any language that can be described as:

{<M>: P(L(M)) = True}

for any nontrivial property P, is not in D.

A nontrivial property is one that is not simply:

True for all languages, or
False for all languages.

Applying Rice’s Theorem

To use Rice’s Theorem to show that a language L is not in D we must:

● Specify property P.

● Show that the domain of P is the SD languages.

● Show that P is nontrivial:

● P is true of at least one language

● P is false of at least one language

Applying Rice’s Theorem

1. {<M> : L(M) contains only even length strings}.

2. {<M> : L(M) contains an odd number of strings}.

3. {<M> : L(M) contains all strings that start with a}.

4. {<M> : L(M) is infinite}.

5. {<M> : L(M) is regular}.

6. {<M> : M contains an even number of states}.

7. {<M> : M has an odd number of symbols in its tape

alphabet}.

8. {<M> : M accepts  within 100 steps}.

9. {<M>: M accepts }.

10. {<Ma, Mb> : L(Ma) = L(Mb)}.

Proof: Let P be any nontrivial property of the SD languages.

H = {<M, w> : TM M halts on input string w}

(?Oracle) L2 = {<M> : P(L(M)) = T}

Either P() = T or P() = F. Assume it is F (a matching proof exists if it is T).

Since P is nontrivial, there is some SD language LT such that P(LT) is T. Let K be some Turing machine that semidecides LT.

Proof of Rice’s Theorem

R(<M, w>) =

1. Construct <M#>, so M#(x) operates as follows:

1.1. Copy its input x to another track for later.

1.2. Erase the tape.

1.3. Write w on the tape.

1.4. Run M on w.

1.5 Put x back on the tape and run K on x.

2. Return <M#>.

Proof of Rice’s Theorem

Recall: K decides LT and we know that P(LT) is True.

Claim: If Oracle exists, C = Oracle(R(<M, w>)) decides H.

Proof:

● R can be implemented as a Turing machine.

● C is correct:

But no machine to decide H can exist, so neither does Oracle.

Proof, Continued

---------------

1. Construct <M#>, so M#(x) operates as follows:

1.1. Copy its input x to another track for later.

1.2. Erase the tape.

1.3. Write w on the tape.

1.4. Run M on w.

1.5 Put x back on the tape and run K on x.

2. Return <M#>.

Proof that R Can Be Implemented

● <M, w>  H: M halts on w. M# makes it to 1.5.

So it is equivalent to K.

L(M#) = L(K) and P(L(M#)) = P(L(K)).

P(L(K)) is T, so P(L(M#)) is T.

Oracle decides P. Oracle accepts.

● <M, w>  H: M does not halt on w. M# gets stuck in 1.4.

So it accepts nothing.

L(M#) = . P() = F.

Oracle decides P. Oracle rejects.

---------------

1. Construct <M#>, so M#(x) operates as follows:

1.1. Copy its input x to another track for later.

1.2. Erase the tape.

1.3. Write w on the tape.

1.4. Run M on w.

1.5 Put x back on the tape and run K on x.

2. Return <M#>.

Proof that C is Correct

Given a TM M, is L(M) Regular?

The problem: Is L(M) regular?

As a language: Is {<M> : L(M) is regular} in D?

No, by Rice’s Theorem:

● P = True if L is regular and False otherwise.

● The domain of P is the set of SD languages since it is

the set of languages accepted by some TM.

● P is nontrivial:

♦ P(a*) = True.

♦ P(AnBn) = False.

Given a Turing Machine M, is L(M) Regular?

H = {<M, w> : TM M halts on input string w}

(Oracle) L2 = {<M> : L(M) is regular}

R(<M, w>) =

1. Construct the description of M#(x):

1.1. Erase tape.

1.2. Write w on the tape.

1.3. Run M on w.

2. Return <M#>.

Is this correct?

Given a Turing Machine M, is L(M) Regular?

H = {<M, w> : TM M halts on input string w}

(Oracle) L2 = {<M> : L(M) is regular}

R(<M, w>) =

1. Construct M#(x):

1.1. Erase tape.

1.2. Write w on the tape.

1.3. Run M on w.

1.4. Accept

2. Return <M#>.

Is this correct?

Given a Turing Machine M, is L(M) Regular?

H = {<M, w> : TM M halts on input string w}

(Oracle) L2 = {<M> : L(M) is regular}

R(<M, w>) =

1. Construct M#(x):

1.1. Copy its input x to another track for later.

1.2. Erase the tape.

1.3. Write w on the tape.

1.4. Run M on w.

1.5. Put x back on the tape.

1.6. If x  AnBn then accept, else reject.

2. Return <M#>.

Problem:

But We Can Flip

R(<M, w>) =

1. Construct the description <M#>, where M#(x) operates as follows:

1.1. Save x for later.

1.2. Erase the tape.

1.3. Write w on the tape.

1.4. Run M on w.

1.5. Put x back on the tape.

1.6. If x  AnBn then accept, else reject.

2. Return <M#>.

If Oracle decides L2, then C = Oracle(R(<M, w>)) decides H:

● <M, w>  H: M# makes it to step 1.5. Then it accepts x iff

x  AnBn. So M# accepts AnBn, which is not regular.

Oracle rejects. C accepts.

● <M, w>  H: M does not halt on w. M# gets stuck in step 1.4.

It accepts nothing. L(M#) = , which is regular.

Oracle accepts. C rejects.

But no machine to decide H can exist, so neither does Oracle.

Or, Doing it Without Flipping

R(<M, w>) =

1. Construct the description <M#>, where M#(x) operates as follows:

1.1. If x  AnBn then accept, else:

1.2. Erase the tape.

1.3. Write w on the tape.

1.4. Run M on w.

1.5. Accept

2. Return <M#>.

If Oracle exists, C = Oracle(R(<M, w>)) decides H:

● C is correct: M# immediately accepts all strings AnBn:

● <M, w>  H: M# accepts everything else in step 1.5. So

L(M#) = *, which is regular. Oracle accepts.

● <M, w>  H: M# gets stuck in step 1.4, so it accepts nothing

else. L(M#) = AnBn, which is not regular. Oracle rejects.

But no machine to decide H can exist, so neither does Oracle.

Any Nonregular Language Will Work

R(<M, w>) =

1. Construct the description <M#>, where M#(x) operates as follows:

1.1. If x  WW then accept, else:

1.2. Erase the tape.

1.3. Write w on the tape.

1.4. Run M on w.

1.5. Accept

2. Return <M#>.

If Oracle exists, C = Oracle(R(<M, w>)) decides H:

● C is correct: M# immediately accepts all strings WW:

● <M, w>  H: M# accepts everything else in step 1.5. So

L(M#) = *, which is regular. Oracle accepts.

● <M, w>  H: M# gets stuck in step 1.4, so it accepts nothing

else. L(M#) = WW, which is not regular. Oracle rejects.

But no machine to decide H can exist, so neither does Oracle.

Is L(M) Context-free?

How about: L3 = {<M> : L(M) is context-free}?

Is L(M) Context-free?

How about: L3 = {<M> : L(M) is context-free}?

R(<M, w>) =

1. Construct the description <M#>, where M#(x) operates as follows:

1.1. If x  AnBnCn then accept, else:

1.2. Erase the tape.

1.3. Write w on the tape.

1.4. Run M on w.

1.5. Accept

2. Return <M#>.

1. Does P, when running on x, halt?

2. Might P get into an infinite loop on some input?

3. Does P, when running on x, ever output a 0? Or anything at

all?

4. Are P1 and P2 equivalent?

5. Does P, when running on x, ever assign a value to n?

6. Does P ever reach S on any input (in other words, can we

chop it out?

7. Does P reach S on every input (in other words, can we

guarantee that S happens)?

● Can the Patent Office check prior art?

● Can the CS department buy the definitive grading program?

Practical Impact of These Results

Turing Machine Questions Can be Reduced to Program Questions

EqPrograms =

{<Pa, Pb> : Pa and Pb are PL programs and L(Pa) = L(Pb)}.

We can build, in any programming language PL, SimUM:

that is a PL program
that implements the Universal TM U and so can simulate an arbitrary TM.

TM Questions and Program Questions

EqPrograms = {<Pa, Pb> : Pa and Pb are PL programs and L(Pa) = L(Pb)}.

Theorem: EqPrograms is not in D.

Proof: Reduction from EqTMs = {<Ma, Mb> : L(Ma) = L(Mb)}.

R(<Ma, Mb>) =

1. Build P1, a PL program that, on w, returns SimUM(Ma, w).

2. Build P2, a PL program that, on w, returns SimUM(Mb, w).

3. Return <P1, P2>.

If Oracle exists and decides EqPrograms, then C = Oracle(R(<Ma, Mb>))

decides EqTMs. C is correct. L(P1) = L(Ma) and L(P2) = L(Mb). So:

● <Ma, Mb>  EqTMs: L(Ma) = L(Mb). So L(P1) = L(P2). Oracle(<P1, P2>)

accepts.

● <Ma, Mb>  EqTMs: L(Ma)  L(Mb). So L(P1)  L(P2). Oracle(<P1, P2>)

rejects.

But no machine to decide EqTMs can exist, so neither does Oracle.

{<M, q> : M reaches q on some input}

HANY = {<M> : there exists some string on which TM M halts}

(?Oracle) L2 = {<M, q> : M reaches q on some input}

R(<M>) =

1. Build <M#> so that M# is identical to M except that, if M has a transition

((q1, c1), (q2, c2, d)) and q2 is a halting state other than h, replace that

transition with:

((q1, c1), (h, c2, d)).

2. Return <M#, h>.

If Oracle exists, then C = Oracle(R(<M>)) decides HANY:

● R can be implemented as a Turing machine.

● C is correct: M# will reach the halting state h iff M would reach some

halting state. So:

● <M>  HANY: There is some string on which M halts. So there is some

string on which M# reaches state h. Oracle accepts.

● <M>  HANY: There is no string on which M halts. So there is no string

on which M# reaches state h. Oracle rejects.

But no machine to decide HANY can exist, so neither does Oracle.

How many Turing machines does it take to change a light bulb?

One.

The Universal Turing Machine

How many Turing machines does it take to change a light bulb?

One.

How can you tell whether your Turing machine is the one?

How many Turing machines does it take to change a light bulb?

One.

How can you tell whether your Turing machine is the one?

You can’t.

- Tim Nodine

There is an uncountable number of non-SD languages, but only a

countably infinite number of TM’s (hence SD languages). The class

of non-SD languages is much bigger than that of SD languages!

Non-SD Languages

Intuition: Non-SD languages usually involve either infinite

search or knowing a TM will infinite loop.

Examples:

H = {<M, w> : TM M does not halt on w}.

{<M> : L(M) = *}.

{<M> : TM M halts on nothing}.

Non-SD Languages

● Contradiction

● L is the complement of an SD/D Language.

● Reduction from a known non-SD language

Proving Languages are not SD

Theorem: TMMIN =

{<M>: Turing machine M is minimal} is not in SD.

Proof: If TMMIN were in SD, then there would exist some Turing

machine ENUM that enumerates its elements. Define the following

Turing machine:

M#(x) =

1. Invoke obtainSelf to produce <M#>.

2. Run ENUM until it generates the description of some Turing

machine M whose description is longer than |<M#>|.

3. Invoke U on the string <M, x>.

Since TMMIN is infinite, ENUM must eventually generate a string that

is longer than |<M#>|. So M# makes it to step 3 and so is equivalent

to M since it simulates M. But, since |<M#>| < |<M>|, M cannot be

minimal. Yet it was generated by ENUM. Contradiction.

Contradiction

Suppose we want to know whether L is in SD and we know:

● L is in SD, and

● At least one of L or L is not in D.

Then we can conclude that L is not in SD, because, if it were,

it would force both itself and its complement into D, which we

know cannot be true.

Example:

● H (since (H) = H is in SD and not in D)

The Compliment of L is in SD/D

Theorem: HANY = {<M> : there does not exist any string on which TM M halts} is not in SD.

Proof: HANY is HANY =

{<M> : there exists at least one string on which TM M

halts}.

We already know:

● HANY is in SD.

● HANY is not in D.

So HANY is not in SD because, if it were, then HANY would be in D but it isn’t.

HANY

Theorem: If there is a reduction R from L1 to L2 and L1 is

not SD, then L2 is not SD.

So, we must:

Choose a language L1 that is known not to be in SD.
Hypothesize the existence of a semideciding TM Oracle.

Note: R may not swap accept for loop.

Using Reduction

H = {<M, w> : TM M does not halt on input string w}

(?Oracle) HANY = {<M> : there does not exist a string

on which TM M halts}

R(<M, w>) =

1. Construct the description <M#> of M#(x):

1.1. Erase the tape.

1.2. Write w on the tape.

1.3. Run M on w.

2. Return <M#>.

Using Reduction for HANY

R(<M, w>) =

1. Construct the description <M#> of M#(x):

1.1. Erase the tape.

1.2. Write w on the tape.

1.3. Run M on w.

2. Return <M#>.

If Oracle exists, then C = Oracle(R(<M, w>)) semidecides H:

● C is correct: M# ignores its input. It halts on everything or

nothing, depending on whether M halts on w. So:

● <M, w>  H: M does not halt on w, so M# halts on

nothing. Oracle accepts.

● <M, w>  H: M halts on w, so M# halts on everything.

Oracle does not accept.

But no machine to semidecide H can exist, so neither does Oracle.

Or We Could Use Reduction for HANY

Aanbn contains strings that look like:

(q00,a00,q01,a00,),

(q00,a01,q00,a10,),

(q00,a10,q01,a01,),

(q00,a11,q01,a10,),

(q01,a00,q00,a01,),

(q01,a01,q01,a10,),

(q01,a10,q01,a11,),

(q01,a11,q11,a01,)

It does not contain strings like aaabbb.

But AnBn does.

Aanbn = {<M> : L(M) = AnBn}

What’s wrong with this proof that Aanbn is not in SD:

H = {<M, w> : TM M does not halt on w}

(?Oracle) Aanbn = {<M> : L(M) = AnBn}

R(<M, w>) =

1. Construct the description <M#>, where M#(x) operates as follows:

1.1. Erase the tape.

1.2. Write w on the tape.

1.3. Run M on w.

1.4. Accept.

2. Return <M#>.

If Oracle exists, C = Oracle(R(<M, w>)) semidecides H:

Aanbn = {<M> : L(M) = AnBn}

If <M, w> is in H, L(M#) = . If <M, w> is not in H, L(M#) is *. Neither is AnBn. So Oracle makes no distinction between the two cases.

What about: H = {<M, w> : TM M does not halt on w}

(?Oracle) Aanbn = {<M> : L(M) = AnBn}

R(<M, w>) =

1. Construct the description <M#>, where M#(x) operates as follows:

1.1 Copy the input x to another track for later.

1.2. Erase the tape.

1.3. Write w on the tape.

1.4. Run M on w.

1.5. Put x back on the tape.

1.6. If x  AnBn then accept, else loop.

2. Return <M#>.

If Oracle exists, C = Oracle(R(<M, w>)) semidecides H:

Aanbn = {<M> : L(M) = AnBn} is not SD

If <M, w> is in H, L(M#) = . If <M, w> is not in H, L(M#) is AnBn. So Oracle gets it backwards.

R(<M, w>) reduces H to Aanbn:

1. Construct the description <M#>:

1.1. If x  AnBn then accept. Else:

1.2. Erase the tape.

1.3. Write w on the tape.

1.4. Run M on w.

1.5. Accept.

2. Return <M#>.

If Oracle exists, then C = Oracle(R(<M, w>)) semidecides H:

M# immediately accepts all strings in AnBn. If M does not halt on

w, those are the only strings M# accepts. If M halts on w,

M# accepts everything:

● <M, w>  H: M does not halt on w, so M# accepts strings in

AnBn in step 1.1. Then it gets stuck in step 1.4, so it accepts

nothing else. It is an AnBn acceptor. Oracle accepts.

● <M, w>  H: M halts on w, so M# accepts everything. Oracle

does not accept.

But no machine to semidecide H can exist, so neither does Oracle.

Aanbn = {<M> : L(M) = AnBn} is not SD

What about: H = {<M, w> : TM M does not halt on w}

(?Oracle) HALL = {<M> : TM halts on *}

Reduction Attempt 1: R(<M, w>) =

1. Construct the description <M#>, where M#(x)

operates as follows:

1.1. Erase the tape.

1.2. Write w on the tape.

1.3. Run M on w.

2. Return <M#>.

HALL = {<M> : TM halts on *}

H = {<M, w> : TM M does not halt on w}

(?Oracle) HALL = {<M> : TM halts on *}

Reduction Attempt 1: R(<M, w>) =

1. Construct the description <M#>, where M#(x) operates as follows:

1.1. Erase the tape.

1.2. Write w on the tape.

1.3. Run M on w.

2. Return <M#>.

If Oracle exists, C = Oracle(R(<M, w>)) semidecides H:

● <M, w>  H: M does not halt on w, so M# gets stuck in step 1.3

and halts on nothing. Oracle does not accept.

● <M, w>  H: M halts on w, so M# halts on everything. Oracle

accepts.

There May Be No Easy Way to Flip

R(<M, w>) reduces H to HALL:

1. Construct the description <M#>, where M#(x) operates as follows:

1.1. Copy the input x to another track for later.

1.2. Erase the tape.

1.3. Write w on the tape.

1.4. Run M on w for |x| steps or until M naturally halts.

1.5. If M naturally halted, then loop.

1.6. Else halt.

2. Return <M#>.

If Oracle exists, C = Oracle(R(<M, w>)) semidecides H:

● <M, w>  H: No matter how long x is, M will not halt in |x|

steps. So, for all inputs x, M# makes it to step 1.6. So it

halts on everything. Oracle accepts.

● <M, w>  H: M halts on w in n steps. On inputs

of length less than n, M# makes it to step 1.6 and halts.

But on all inputs of length n or greater, M# will loop in step

1.5. Oracle does not accept.

HALL = {<M> : TM halts on *}

EqTMs = {<Ma, Mb> : L(Ma) = L(Mb)}

We’ve already shown it’s not in D.

Now we show it’s also not in SD.

EqTMs = {<Ma, Mb> : L(Ma) = L(Mb)}

H = {<M, w> : TM M does not halt on w}

(?Oracle) EqTMs = {<Ma, Mb> : L(Ma) = L(Mb)}

R(<M, w>) =

1. Construct the description <M#>:

2. Construct the description <M?>:

3. Return <M#, M?>.

If Oracle exists, C = Oracle(R(<M, w>)) semidecides H:

● <M, w>  H:

● <M, w>  H:

EqTMs = {<Ma, Mb> : L(Ma) = L(Mb)}

R(<M, w>) =

1. Construct the description <M#>:

1.1 Erase the tape.

1.2 Write w on the tape.

1.3 Run M on w.

1.4 Accept.

2. Construct the description <M?>:

1.1 Loop.

3. Return <M#, M?>.

If Oracle exists, C = Oracle(R(<M, w>)) semidecides H: M? halts on nothing.

● <M, w>  H: M does not halt on w, so M# gets stuck

in step 1.3 and halts on nothing. Oracle accepts.

● <M, w>  H: M halts on w, so M# halts on

everything. Oracle does not accept.

L1 = {<M>: M has an even number of states}.

L2 = {<M>: |<M>| is even}.

L3 = {<M>: |L(M)| is even}.

L4 = {<M>: M accepts all even length strings}.

The Details Matter

L1 = {<M>: M has an even number of states}.

L2 = {<M>: |<M>| is even}.

L3 = {<M>: |L(M)| is even}.

H M L3: R(<M, w>) =

1. Construct the description <M#>, where M#(x) operates as follows:

1.1 Copy the input x to another track for later.

1.2 Erase the tape.

1.3 Write w on the tape.

1.4 Run M on w.

1.5 If x =  then accept. Else loop.

2. Return <M#>.

● <M, w>  H:

● <M, w>  H:

The Details Matter

L1 = {<M>: M has an even number of states}.

L2 = {<M>: |<M>| is even}.

L3 = {<M>: |L(M)| is even}.

L4 = {<M>: M accepts all even length strings}.

The Details Matter

L1 = {<M>: M has an even number of states}.

L2 = {<M>: |<M>| is even}.

L3 = {<M>: |L(M)| is even}.

L4 = {<M>: M accepts all even length strings}

The Details Matter

H M L4: R(<M, w>) =

1. Construct the description <M#>, where M#(x) operates as follows:

1.1 Copy the input x to another track for later.

1.2 Erase the tape.

1.3 Write w on the tape.

1.4 Run M on w for |x| steps or until M naturally halts.

1.5 If M halted naturally, then loop. Else accept.

2. Return <M#>.

● <M, w>  H:

● <M, w>  H:

Consider :

L1 = {<M, w>: M rejects w}.

L2 = {<M, w>: M does not halt on w}.

L3 = {<M, w>: M is a deciding TM and rejects w}.

Accepting, Rejecting, Halting, and Looping

{<M, w>: M is a Deciding TM and Rejects w}

H = {<M, w> : TM M does not halt on w}

(?Oracle) {<M, w>: M is a deciding TM and rejects w}

R(<M, w>) =

1. Construct the description <M#>, where M#(x) operates as follows:

1.1 Erase the tape.

1.2 Write w on the tape.

1.3 Run M on w.

1.4 Reject.

2. Return <M#, >.

If Oracle exists, C = Oracle(R(<M, w>)) semidecides H:

● <M, w>  H:

● <M, w>  H:

Problem:

If <M, w>  H, then M# isn’t a decider. So Oracle fails to accept.

{<M, w>: M is a Deciding TM and Rejects w}

HALL = {<M> : TM M halts on *}

(?Oracle) {<M, w>: M is a deciding TM and rejects w}

R(<M>) =

1. Construct the description <M#>, where M#(x) operates as follows:

1.1 Run M on x.

1.2 Reject.

2. Return <M#, >.

If Oracle exists, C = Oracle(R(<M>)) semidecides HALL:

● <M>  HALL: M# halts and rejects all inputs. Oracle accepts.

● <M>  HALL: There is at least one input on which M doesn’t halt. So M# is not a deciding TM. Oracle does not accept.

No machine to semidecide HALL can exist, so neither does Oracle.

What About These?

L1 = {a}.

L2 = {<M> : M accepts a}.

L3 = {<M> : L(M) = {a}}.

What About These?

L1 = {a}.

L2 = {<M> : M accepts a}.

L3 = {<M> : L(M) = {a}}.

H M L3: R(<M, w>) =

1. Construct the description <M#>, where M#(x) operates as follows:

1.1 If x = a, accept.

1.2 Erase the tape.

1.2 Write w on the tape.

1.3 Run M on w.

1.4 Accept.

2. Return <M#>.

● <M, w>  H:

● <M, w>  H:

<M, w>  H: L(M#) = {a}.

<M, w>  H: L(M#) = *.

{<Ma, Mb> :   L(Ma) – L(Mb)}

R( ) =

Return <M?, M#>.

<M, w>  H: L(M?) - L(M#) =

<M, w>  H: L(M?) - L(M#) =

{<Ma, Mb> :   L(Ma) – L(Mb)}

R is a reduction from H. R(<M, w>) =

1. Construct the description of M#(x) that operates as follows:

1.1. Erase the tape.

1.2. Write w.

1.3. Run M on w.

1.4. Accept.

2. Construct the description of M?(x) that operates as follows:

2.1. Accept.

3. Return <M?, M#>.

If Oracle exists and semidecides L, C = Oracle(R(<M, w>))

semidecides H: M? accepts everything, including . So:

<M, w>  H: L(M?) - L(M#) =

<M, w>  H: L(M?) - L(M#) =

<M, w>  H: L(M?) - L(M#) = * -  = *.
<M, w>  H: L(M?) - L(M#) = * - *= .

The Problem View	The Language View	Status
Does TM M have an even number of states?	{<M> : M has an even number of states}	D
Does TM M halt on w?	H = {<M, w> : M halts on w}	SD/D
Does TM M halt on the empty tape?	H = {<M> : M halts on }	SD/D
Is there any string on which TM M halts?	HANY = {<M> : there exists at least one string on which TM M halts }	SD/D
Does TM M halt on all strings?	HALL = {<M> : M halts on *}	SD
Does TM M accept w?	A = {<M, w> : M accepts w}	SD/D
Does TM M accept ?	A = {<M> : M accepts }	SD/D
Is there any string that TM M accepts?	AANY {<M> : there exists at least one string that TM M accepts }	SD/D

Does TM M accept all strings?	AALL = {<M> : L(M) = *}	SD
Do TMs Ma and Mb accept the same languages?	EqTMs = {<Ma, Mb> : L(Ma) = L(Mb)}	SD

Does TM M not halt on any string?	HANY = {<M> : there does not exist any string on which M halts}	SD
Does TM M not halt on its own description?	{<M> : TM M does not halt on input <M>}	SD
Is TM M minimal?	TMMIN = {<M>: M is minimal}	SD
Is the language that TM M accepts regular?	TMreg = {<M> : L(M) is regular}	SD
Does TM M accept the language AnBn?	Aanbn = {<M> : L(M) = AnBn}	SD

IN SD OUT

Semideciding TM H Reduction

Enumerable

Unrestricted grammar

Deciding TM AnBnCn Diagonalize

Lexico. enum Reduction

L and L in SD

Context-Free

CF grammar AnBn Pumping

PDA Closure

Closure

Regular

Regular Expression a*b* Pumping

FSM Closure

Language Summary