Decidable ? Not Decidable ?

Decidable.md

✓Decidable

DFA NFA Regular Expression

1. A_DFA = {< D, w > | D is a DFA that accepts input w}
   By Simulatation
2. A_NFA = {< N, w > | N is an NFA that accepts input w}
   Convert to DFA
3. A_REX = {< R, w > | R is a regular expression that generates w}
   Convert to DFA
4. MIN_DFA = {< D > | D is a minimal DFA}
   Use minimization alg
5. EQ_DFA = {< D₁, D₂ > | D₁, D₂ are DFAs and L(D₁) = L(D₂)}
   Use minimization alg on both
6. E_DFA = {< D > | D is DFA and L(D) is empty}
   Check EQ with < D, ->O >

CFG CFL

1. A_CFG = {< G, w > | G is a CFG that generates w}
   Elimate ε- and unit productions from G
   Convert G into CNF G'
   Check if can CYK Alg prase < G', w >
2. L accept w where L is a context-free language
   onvert to CFG

✗Not Decidable

CFG

1. EQ_CFG = {< G₁, G₂ > | G₁, G₂ are CFGs and L(G₁) = L(G₂)}
2. ALL_CFG = {< G > | G is CFG that generates all strings}
   Construct a PDA P accepts all string except the computation histories of (M, w)
   Convert P to a CFG G
   Run R on input < G >
   S accepts if R accepts; S rejects if R rejects
   S accepts iff G reject the computation histories of (M, w), only when know M accept w
   S decides NOT A_TM
3. AMB = {< G > | G is an ambiguous CFG}
   If T can match, G is ambiguous
   If T cannot match, G is not ambiguous
   Construct G by
   S -> T | B
   T -> (Top of tile 1)T1 | (Top of tile 2)T2 | ... | (Top of tile n)Tn
   T -> (Top of tile 1)1 | (Top of tile 2)2 | ... | (Top of tile n)n
   B -> (Bottom of tile 1)B1 | (Bottom of tile 2)B2 | ... | (Bottom of tile n)Bn
   B -> (Bottom of tile 1)1 | (Bottom of tile 2)2 | ... | (Bottom of tile n)n
   T can match, Strings (TopTileA)(TopTileB)(TopTileC)CBA and (BotTileA)(BotTileB)(BotTileC)CBA will be in G and they are the same with two different way to parse
   G is ambiguous

PCP

1. PCP = {< T > | T is a collection of tiles that contains a top-bottom match} Proof is outc

TM

1. A_TM = { < M, w > | M is a TM that accepts input w}
   Assume A_TM is decidable, then some TM H decides A_TM
   Construct a TM D, on input < M >
   1. Run H on input < M, < M > >
   2. Accept if H reject; Reject if H accept
   i.e. D accept if M loop or reject < M >, D reject if M accept < M >
   Run D with input < D >
   D accept if D reject < D >, D reject if D accept < D >
   Contradiction
2. NOT A_TM = { < M, w > | M is a TM that reject or loop on input w}
   If NOT A_TM is decidable, then A_TM is decidable as A_TM is recognizable
3. HALT_TM = { < M, w > | M is a TM that halt on input w}
   Use HALT_TM to reject the loop on case in A_TM
4. ε_TM = { < M > | M is a TM that accepts input ε}
   M' accepts z if M accepts w
   S know ε only when know if M' accept any z, when know if M accpet w
5. SOME_TM = { < M > | M is a TM that accepts some input strings}
   M' accepts z if M accepts w
   S know some input z is accepted or not only when know if M' accept some z, when know if M accpet w
6. E_TM = { < M > | M is a TM that accepts no input strings}
   M' accepts z if M accepts w
   S know all input z is rejcted or not only when know if M' accept any z, when know if M accpet w
   --OR--
   Run R on input < M >
   S accpets if R rejects; S rejects if R accepts
   S accpets iff M accept some input So S decides SOME_TM
7. EQ_TM = { < M₁, M₂ > | M₁, M₂ are a TMs such that L(M₁) = L(M₂)}
   Construct M₂ reject all z
   Run R on input < M, M₂ >
   S accepts if R acceptes; S rejects if R rejects
   S accepts iff M accept no input So S decides E_TM

Format of proving a problem is undeciable

Let say A is the problem
Main idea is to reduce decider of problem A to decider of A_TM
i.e. Solve A -> A_TM is solved

1. Suppose A is decidable
2. Let R be a TM that decides A
3. Consider the TM S: on input < M, w >, and try to claim S decide A_TM
4. Construct the following TM M':
   M' = a TM such that on input z,
   Simulate M on input w and accept/reject z according to M' (or use other undecidable problem to generate problem A)
5. Run R on input < M' (, and / or something else) > and S accepts/rejects according H (or reverse)>
6. Then S accept < M, w > if and only if M accept w
7. So S decides A_TM, which is impossible
8. So R does not exist