{\rtf1\ansi\ansicpg1252\uc1 \deff0\deflang1033\deflangfe1033{\fonttbl{\f0\froman\fcharset0\fprq2{\*\panose 02020603050405020304}Times New Roman;}}{\colortbl;\red0\green0\blue0;\red0\green0\blue255;\red0\green255\blue255;\red0\green255\blue0;
\red255\green0\blue255;\red255\green0\blue0;\red255\green255\blue0;\red255\green255\blue255;\red0\green0\blue128;\red0\green128\blue128;\red0\green128\blue0;\red128\green0\blue128;\red128\green0\blue0;\red128\green128\blue0;\red128\green128\blue128;
\red192\green192\blue192;}{\stylesheet{\widctlpar\adjustright \fs20\cgrid \snext0 Normal;}{\s1\qc\keepn\widctlpar\adjustright \b\fs20\cgrid \sbasedon0 \snext0 heading 1;}{\s2\keepn\widctlpar\adjustright \cgrid \sbasedon0 \snext0 heading 2;}{\*\cs10 
\additive Default Paragraph Font;}{\s15\widctlpar\tqc\tx4320\tqr\tx8640\adjustright \fs20\cgrid \sbasedon0 \snext15 header;}{\s16\widctlpar\tqc\tx4320\tqr\tx8640\adjustright \fs20\cgrid \sbasedon0 \snext16 footer;}{\*\cs17 \additive \sbasedon10 
page number;}}{\*\listtable{\list\listtemplateid259955080\listsimple{\listlevel\levelnfc0\leveljc0\levelfollow0\levelstartat4\levelspace0\levelindent0{\leveltext\'02\'00.;}{\levelnumbers\'01;}\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname 
;}\listid1793740694}}{\*\listoverridetable{\listoverride\listid1793740694\listoverridecount0\ls1}}{\info{\title HUMBOLDT STATE UNIVERSITY}{\author Dr. Hal Campbell}{\operator Tuttle}{\creatim\yr2000\mo4\dy5\hr15\min21}{\revtim\yr2000\mo4\dy5\hr15\min21}
{\printim\yr1999\mo3\dy10\hr11\min37}{\version2}{\edmins0}{\nofpages1}{\nofwords638}{\nofchars3638}{\*\company CNRS - HSU}{\nofcharsws4467}{\vern113}}\widowctrl\ftnbj\aenddoc\lytprtmet\formshade\viewkind1\viewscale100\pgbrdrhead\pgbrdrfoot \fet0\sectd 
\linex0\endnhere\sectdefaultcl {\header \pard\plain \s15\widctlpar\tqc\tx4320\tqr\tx8640\adjustright \fs20\cgrid {\fs18 CIS 480 - Reduction Template\tab \tab p. }{\field{\*\fldinst {\cs17\fs18  PAGE }}{\fldrslt {\cs17\fs18\lang1024 1}}}{\fs18 
\par Sharon Tuttle - Spring 2000
\par }}{\*\pnseclvl1\pnucrm\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl2\pnucltr\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl3\pndec\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl4\pnlcltr\pnstart1\pnindent720\pnhang{\pntxta )}}
{\*\pnseclvl5\pndec\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl6\pnlcltr\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl7\pnlcrm\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl8
\pnlcltr\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl9\pnlcrm\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}\pard\plain \s1\qc\keepn\widctlpar\outlinelevel0\adjustright \b\fs20\cgrid {CIS 480 - Reduction Template - Spring 2000
\par }\pard\plain \fi-360\li360\widctlpar\adjustright \fs20\cgrid {\tab 
\par }\pard \widctlpar\adjustright {\b Note the following required format (for this class) for showing that a problem is undecidable by use of a reduction:
\par 
\par }\pard\plain \s2\keepn\widctlpar\outlinelevel1\adjustright \cgrid {\b\fs20\lang1024 {\shp{\*\shpinst\shpleft-96\shptop24\shpright8856\shpbottom6024\shpfhdr0\shpbxcolumn\shpbypara\shpwr3\shpwrk0\shpfblwtxt0\shpz0\shplid1027
{\sp{\sn shapeType}{\sv 1}}{\sp{\sn fFlipH}{\sv 0}}{\sp{\sn fFlipV}{\sv 0}}{\sp{\sn fFilled}{\sv 0}}}{\shprslt{\*\do\dobxcolumn\dobypara\dodhgt8192\dprect\dpx-96\dpy24\dpxsize8952\dpysize6000
\dpfillfgcr255\dpfillfgcg255\dpfillfgcb255\dpfillbgcr255\dpfillbgcg255\dpfillbgcb255\dpfillpat0\dplinew15\dplinecor0\dplinecog0\dplinecob0}}}}{\b\fs20 CIS 480 REDUCTION TEMPLATE:
\par }\pard\plain \fi-360\li360\widctlpar\adjustright \fs20\cgrid {\b 1.\tab state the problem, giving it a name, also:
\par }\pard \widctlpar\adjustright {*   Consider problem }{\b X}{, the (yes/no) problem determining whether }{\b Y}{.}{\b 
\par }{\b\fs24 
\par }\pard \fi-360\li360\widctlpar\adjustright {\b 2.\tab make the following statement of your purpose:
\par }\pard \widctlpar\adjustright {        *   We use the undecidability of }{\b <known undecidable problem>}{ to prove the 
\par         undecidability of }{\b X}{ by reducing }{\b <known undecidable problem>}{ to }{\b X}{.}{\b 
\par }{\b\fs24 
\par }\pard \fi-360\li360\widctlpar\adjustright {\b 3.\tab explicitly state your assumption:
\par }\pard \widctlpar\adjustright {\b         }{*   ASSUME we have a TM R that decides }{\b X}{.
\par }\pard \fi-360\li360\widctlpar\adjustright {
\par {\pntext\pard\plain\b\fs20\cgrid \hich\af0\dbch\af0\loch\f0 4.\tab}}\pard \fi-360\li360\widctlpar\jclisttab\tx360{\*\pn \pnlvlbody\ilvl0\ls1\pnrnot0\pndec\pnstart4\pnindent360\pnhang{\pntxta .}}\ls1\adjustright {\b 
make the following statement, followed by the appropriate TM, stated using the same 
\par }\pard \li360\widctlpar\adjustright {\b standards as used in the CIS 480 DECIDABILITY TEMPLATE:
\par }\pard \widctlpar\adjustright {\b         }{*   Use R to construct S, a TM that decides }{\b <known undecidable problem>}{.
\par }{\b         }{*   S = "On input \'85
\par }{\b                 }{1. 
\par                 2. 
\par                 \'85
\par }{\fs24 
\par }\pard \fi-360\li360\widctlpar\adjustright {\b 5.\tab give an appropriate concluding statement:
\par }\pard \widctlpar\adjustright {        *   If R decides }{\b X}{, then S decides }{\b <known undecidable problem>}{. CONTRADICTION;
\par }{\b         }{*   Because }{\b <known undecidable problem>}{ is undecidable, we know that there can 
\par         be NO decider/algorithm for }{\b <known undecidable problem>}{; so, }{\b X}{ also must be 
\par         undecidable.}{\b 
\par 
\par }}