richardfat7/Decidable.html

## Decidable.html
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=utf-8">
</head>
<body>
<h1>Decidable</h1>
<h2>DFA NFA Regular Expression</h2>
<ol>
<li>A<sub>DFA</sub> = {&lt; D, w &gt; | D is a DFA that accepts input w}<blockquote>
<p>By Simulatation</p>
</blockquote>
</li>
<li>A<sub>NFA</sub> = {&lt; N, w &gt; | N is an NFA that accepts input w}<blockquote>
<p>Convert to DFA</p>
</blockquote>
</li>
<li>A<sub>REX</sub> = {&lt; R, w &gt; | R is a regular expression that generates w}<blockquote>
<p>Convert to DFA</p>
</blockquote>
</li>
<li>MIN<sub>DFA</sub> = {&lt; D &gt; | D is a minimal DFA}<blockquote>
<p>Use minimization alg</p>
</blockquote>
</li>
<li>EQ<sub>DFA</sub> = {&lt; D<sub>1</sub>, D<sub>2</sub> &gt; | D<sub>1</sub>, D<sub>2</sub> are DFAs and L(D<sub>1</sub>) = L(D<sub>2</sub>)}<blockquote>
<p>Use minimization alg on both</p>
</blockquote>
</li>
<li>E<sub>DFA</sub> = {&lt; D &gt; | D is DFA and L(D) is empty}<blockquote>
<p>Check EQ with &lt; D, -&gt;O &gt;</p>
</blockquote>
</li>
</ol>
<h2>CFG CFL</h2>
<ol>
<li>A<sub>CFG</sub> = {&lt; G, w &gt; | G is a CFG that generates w}<blockquote>
<p>Elimate ε- and unit productions from G<br>
Convert G into CNF G'<br>
Check if can CYK Alg prase &lt; G', w &gt;   </p>
</blockquote>
</li>
<li>L accept w where L is a context-free language<blockquote>
<p>Convert to CFG</p>
</blockquote>
</li>
</ol>
<h1>Not Decidable</h1>
<h2>CFG</h2>
<ol>
<li>EQ<sub>CFG</sub> = {&lt; G<sub>1</sub>, G<sub>2</sub> &gt; | G<sub>1</sub>, G<sub>2</sub> are CFGs and L(G<sub>1</sub>) = L(G<sub>2</sub>)}</li>
<li>A<sub>TM</sub> = { &lt; M, w &gt; | M is a TM that accepts input w}<blockquote>
<p>Assume A<sub>TM</sub> is decidable, then some TM H decides A<sub>TM</sub> <br>
Construct a TM D, on input &lt; M &gt;<br>
1. Run H on input &lt; M, &lt; M &gt; &gt; <br>
2. Accept if H reject; Reject if H accept   <br>
i.e. D accept if M loop or reject &lt; M &gt;, D reject if M accept &lt; M &gt; <br>
Run D with input &lt; D &gt; <br>
D accept if D reject &lt; D &gt;, D reject if D accept &lt; D &gt; <br>
Contradiction   </p>
</blockquote>
</li>
<li>NOT A<sub>TM</sub> = { &lt; M, w &gt; | M is a TM that reject or loop on input w}<blockquote>
<p>If NOT A<sub>TM</sub> is decidable, then A<sub>TM</sub> is decidable as A<sub>TM</sub> is recognizable</p>
</blockquote>
</li>
<li>HALT<sub>TM</sub> = { &lt; M, w &gt; | M is a TM that halt on input w}<blockquote>
<p>Use HALT<sub>TM</sub> to reject the loop on case in A<sub>TM</sub></p>
</blockquote>
</li>
<li>ε<sub>TM</sub> = { &lt; M &gt; | M is a TM that accepts input ε
}<blockquote>
<p>M' accepts z if M accepts w <br>
know ε only when know if M' accept any z, when know if M accpet w</p>
</blockquote>
</li>
<li>SOME<sub>TM</sub> = { &lt; M &gt; | M is a TM that accepts some input strings
}<blockquote>
<p>M' accepts z if M accepts w <br>
know some input z is accepted or not only when know if M' accept some z, when know if M accpet w</p>
</blockquote>
</li>
<li>E<sub>TM</sub> = { &lt; M &gt; | M is a TM that accepts no input strings
}<blockquote>
<p>M' accepts z if M accepts w <br>
know all input z is rejcted or not only when know if M' accept any z, when know if M accpet w <br>
--OR--<br>
Run R on input &lt; M &gt; <br>
S accpets if R rejects; S rejects if R accepts <br>
S accpets iff M accept some input
So S decides SOME<sub>TM</sub>  </p>
</blockquote>
</li>
<li>EQ<sub>TM</sub> = { &lt; M<sub>1</sub>, M<sub>2</sub> &gt; | M<sub>1</sub>, M<sub>2</sub> are a TMs such that L(M<sub>1</sub>) = L(M<sub>2</sub>)}<blockquote>
<p>Construct M<sub>2</sub> reject all z <br>
Run R on input &lt; M, M<sub>2</sub> &gt; <br>
S accepts if R acceptes; S rejects if R rejects<br>
S accepts iff M accept no input
So S decides E<sub>TM</sub></p>
</blockquote>
</li>
</ol>
<h1>Format of proving a problem is undeciable</h1>
<p>Let say A is the problem <br>
Main idea is to reduce decider of problem A to decider of  A<sub>TM</sub> <br>
i.e. Solve A -&gt; A<sub>TM</sub> is solved</p>
<ol>
<li>Suppose A is decidable</li>
<li>Let R be a TM that decides A</li>
<li>Consider the TM S: on input &lt; M, w &gt;, and try to claim S decide A<sub>TM</sub></li>
<li>Construct the following TM M':<br>
        M' = a TM such that on input z, <br>
        Simulate M on input w and accept/reject z according to M' (<strong>or use other undecidable problem to generate problem A</strong>)</li>
<li>Run R on input &lt; M' (, and / or something else) &gt; and S accepts/rejects according H (or reverse)&gt;</li>
<li>Then S accept &lt; M, w &gt; if and only if M accept w</li>
<li>So S decides A<sub>TM</sub>, which is impossible   </li>
<li>So R does not exist  </li>
</ol>
</body>
</html>
	<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
	<html>
	<head>
	<meta http-equiv="content-type" content="text/html; charset=utf-8">
	</head>
	<body>
	<h1>Decidable</h1>
	<h2>DFA NFA Regular Expression</h2>
	<ol>
	<li>A<sub>DFA</sub> = {< D, w > \| D is a DFA that accepts input w}<blockquote>
	<p>By Simulatation</p>
	</blockquote>
	</li>
	<li>A<sub>NFA</sub> = {< N, w > \| N is an NFA that accepts input w}<blockquote>
	<p>Convert to DFA</p>
	</blockquote>
	</li>
	<li>A<sub>REX</sub> = {< R, w > \| R is a regular expression that generates w}<blockquote>
	<p>Convert to DFA</p>
	</blockquote>
	</li>
	<li>MIN<sub>DFA</sub> = {< D > \| D is a minimal DFA}<blockquote>
	<p>Use minimization alg</p>
	</blockquote>
	</li>
	<li>EQ<sub>DFA</sub> = {< D<sub>1</sub>, D<sub>2</sub> > \| D<sub>1</sub>, D<sub>2</sub> are DFAs and L(D<sub>1</sub>) = L(D<sub>2</sub>)}<blockquote>
	<p>Use minimization alg on both</p>
	</blockquote>
	</li>
	<li>E<sub>DFA</sub> = {< D > \| D is DFA and L(D) is empty}<blockquote>
	<p>Check EQ with < D, ->O ></p>
	</blockquote>
	</li>
	</ol>
	<h2>CFG CFL</h2>
	<ol>
	<li>A<sub>CFG</sub> = {< G, w > \| G is a CFG that generates w}<blockquote>
	<p>Elimate ε- and unit productions from G<br>
	Convert G into CNF G'<br>
	Check if can CYK Alg prase < G', w > </p>
	</blockquote>
	</li>
	<li>L accept w where L is a context-free language<blockquote>
	<p>Convert to CFG</p>
	</blockquote>
	</li>
	</ol>
	<h1>Not Decidable</h1>
	<h2>CFG</h2>
	<ol>
	<li>EQ<sub>CFG</sub> = {< G<sub>1</sub>, G<sub>2</sub> > \| G<sub>1</sub>, G<sub>2</sub> are CFGs and L(G<sub>1</sub>) = L(G<sub>2</sub>)}</li>
	<li>A<sub>TM</sub> = { < M, w > \| M is a TM that accepts input w}<blockquote>
	<p>Assume A<sub>TM</sub> is decidable, then some TM H decides A<sub>TM</sub> <br>
	Construct a TM D, on input < M ><br>
	1. Run H on input < M, < M > > <br>
	2. Accept if H reject; Reject if H accept <br>
	i.e. D accept if M loop or reject < M >, D reject if M accept < M > <br>
	Run D with input < D > <br>
	D accept if D reject < D >, D reject if D accept < D > <br>
	Contradiction </p>
	</blockquote>
	</li>
	<li>NOT A<sub>TM</sub> = { < M, w > \| M is a TM that reject or loop on input w}<blockquote>
	<p>If NOT A<sub>TM</sub> is decidable, then A<sub>TM</sub> is decidable as A<sub>TM</sub> is recognizable</p>
	</blockquote>
	</li>
	<li>HALT<sub>TM</sub> = { < M, w > \| M is a TM that halt on input w}<blockquote>
	<p>Use HALT<sub>TM</sub> to reject the loop on case in A<sub>TM</sub></p>
	</blockquote>
	</li>
	<li>ε<sub>TM</sub> = { < M > \| M is a TM that accepts input ε
	}<blockquote>
	<p>M' accepts z if M accepts w <br>
	know ε only when know if M' accept any z, when know if M accpet w</p>
	</blockquote>
	</li>
	<li>SOME<sub>TM</sub> = { < M > \| M is a TM that accepts some input strings
	}<blockquote>
	<p>M' accepts z if M accepts w <br>
	know some input z is accepted or not only when know if M' accept some z, when know if M accpet w</p>
	</blockquote>
	</li>
	<li>E<sub>TM</sub> = { < M > \| M is a TM that accepts no input strings
	}<blockquote>
	<p>M' accepts z if M accepts w <br>
	know all input z is rejcted or not only when know if M' accept any z, when know if M accpet w <br>
	--OR--<br>
	Run R on input < M > <br>
	S accpets if R rejects; S rejects if R accepts <br>
	S accpets iff M accept some input
	So S decides SOME<sub>TM</sub> </p>
	</blockquote>
	</li>
	<li>EQ<sub>TM</sub> = { < M<sub>1</sub>, M<sub>2</sub> > \| M<sub>1</sub>, M<sub>2</sub> are a TMs such that L(M<sub>1</sub>) = L(M<sub>2</sub>)}<blockquote>
	<p>Construct M<sub>2</sub> reject all z <br>
	Run R on input < M, M<sub>2</sub> > <br>
	S accepts if R acceptes; S rejects if R rejects<br>
	S accepts iff M accept no input
	So S decides E<sub>TM</sub></p>
	</blockquote>
	</li>
	</ol>
	<h1>Format of proving a problem is undeciable</h1>
	<p>Let say A is the problem <br>
	Main idea is to reduce decider of problem A to decider of A<sub>TM</sub> <br>
	i.e. Solve A -> A<sub>TM</sub> is solved</p>
	<ol>
	<li>Suppose A is decidable</li>
	<li>Let R be a TM that decides A</li>
	<li>Consider the TM S: on input < M, w >, and try to claim S decide A<sub>TM</sub></li>
	<li>Construct the following TM M':<br>
	M' = a TM such that on input z, <br>
	Simulate M on input w and accept/reject z according to M' (<strong>or use other undecidable problem to generate problem A</strong>)</li>
	<li>Run R on input < M' (, and / or something else) > and S accepts/rejects according H (or reverse)></li>
	<li>Then S accept < M, w > if and only if M accept w</li>
	<li>So S decides A<sub>TM</sub>, which is impossible </li>
	<li>So R does not exist </li>
	</ol>
	</body>
	</html>