<div class="xblock xblock-public_view xblock-public_view-vertical" data-graded="False" data-init="VerticalStudentView" data-has-score="False" data-block-type="vertical" data-course-id="course-v1:MITx+24.118x+2T2020" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@26332bda631e4365b8d113874513704b" data-request-token="f97aa7d65ad011efb7210affdd549e9b" data-runtime-class="LmsRuntime" data-runtime-version="1">
<h2 class="hd hd-2 unit-title">Turing Machines</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@25776ef166bc4dc6b860276f91630bc3">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-graded="False" data-init="XBlockToXModuleShim" data-has-score="False" data-block-type="html" data-course-id="course-v1:MITx+24.118x+2T2020" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@25776ef166bc4dc6b860276f91630bc3" data-request-token="f97aa7d65ad011efb7210affdd549e9b" data-runtime-class="LmsRuntime" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p><span style="font-size: 12pt; font-family: book antiqua,palatino;"><span style="font-size: 12pt;">Let me start by introducing you to <strong>Turing Machines</strong>, which are computers of a particularly simple sort. They are named after their creator, the great British mathematician and hero of the Second World War, Alan Turing.<strong></strong></span></span></p>
<p><span style="font-size: 12pt; font-family: book antiqua,palatino;"><span style="font-size: 12pt;"><strong></strong>A Turing Machine’s <strong>hardware</strong> consists of two components, a memory tape and a tape-reader: </span></span></p>
<p style="padding-left: 30px;"><span style="font-family: 'book antiqua', palatino;"><strong>The Memory tape</strong></span><br /><span style="font-family: 'book antiqua', palatino;">You can think of the tape as a long strip of paper, divided into cells:</span></p>
<center>
<p><span style="font-size: 12pt; font-family: book antiqua,palatino;"><span style="font-size: 12pt;"><img src="https://studio.edx.org/asset-v1:MITx+24.118x+1T2018+type@asset+block@FiguresDiagramsParadoxInfinity-21.png" type="saveimage" target="[object Object]" width="989" height="252" /><br /></span></span></p>
</center>
<p><span style="font-size: 12pt; font-family: book antiqua,palatino;">The tape is assumed to be infinite in both directions. (Alternatively, one might assume a finite tape, and an assistant who is ready to add paper to either end, as needed.) </span></p>
<p style="padding-left: 30px;"><span style="font-family: 'book antiqua', palatino;"><strong>The Tape-reader</strong></span><br /><span style="font-family: 'book antiqua', palatino;">At any given time, the machine’s “reader” sits on a particular cell of the memory tape, and is able to perform the following functions:</span></p>
<ul style="padding-left: 30px;">
<li><span style="font-family: book antiqua,palatino;">Read the symbol written on the cell</span></li>
<li><span style="font-family: book antiqua,palatino;">Write a new symbol on the cell</span></li>
<li><span style="font-family: book antiqua,palatino;">Move one cell to the left</span></li>
<li><span style="font-family: book antiqua,palatino;">Move one cell to the right</span></li>
</ul>
<p><span style="font-family: book antiqua,palatino;">We will indicate the position of the reader in our diagrams by placing arrow beneath the cell at which the reader is positioned:</span></p>
<center>
<p><span style="font-family: book antiqua,palatino;"><img src="https://studio.edx.org/asset-v1:MITx+24.118x+1T2018+type@asset+block@FiguresDiagramsParadoxInfinity-21final.png" alt="" type="saveimage" target="[object Object]" preventdefault="function (){r.isDefaultPrevented=n}" stoppropagation="function (){r.isPropagationStopped=n}" stopimmediatepropagation="function (){r.isImmediatePropagationStopped=n}" isdefaultprevented="function t(){return!1}" ispropagationstopped="function t(){return!1}" isimmediatepropagationstopped="function t(){return!1}" width="981" height="261" /></span></p>
</center>
<p></p>
<p><span style="font-family: book antiqua,palatino;">A Turing Machine’s <strong>software</strong> (i.e. the computer program it implements) consists of a finite list of <strong>command lines.</strong> Each command line is a sequence of five symbols, corresponding to the following parameters:</span></p>
<center>
<p><span style="font-family: book antiqua,palatino;">[mathjaxinline]\langle[/mathjaxinline]current state [mathjaxinline]\rangle[/mathjaxinline][mathjaxinline]\langle[/mathjaxinline]current symbol [mathjaxinline]\rangle[/mathjaxinline][mathjaxinline]\langle[/mathjaxinline]new symbol [mathjaxinline]\rangle[/mathjaxinline][mathjaxinline]\langle[/mathjaxinline]direction [mathjaxinline]\rangle[/mathjaxinline][mathjaxinline]\langle[/mathjaxinline]new state [mathjaxinline]\rangle[/mathjaxinline]</span></p>
</center>
<p><span style="font-family: book antiqua,palatino;">Think of a command line as encoding the following instruction:</span></p>
<blockquote>
<p><span style="font-family: book antiqua,palatino;">If you are in [mathjaxinline]\langle[/mathjaxinline]current state [mathjaxinline]\rangle[/mathjaxinline] and your reader sees [mathjaxinline]\langle[/mathjaxinline]current symbol [mathjaxinline]\rangle[/mathjaxinline] written on the memory tape, replace [mathjaxinline]\langle[/mathjaxinline]current symbol [mathjaxinline]\rangle[/mathjaxinline] with [mathjaxinline]\langle[/mathjaxinline]new symbol [mathjaxinline]\rangle[/mathjaxinline]. Then move one step in direction [mathjaxinline]\langle[/mathjaxinline]direction [mathjaxinline]\rangle[/mathjaxinline], and go to [mathjaxinline]\langle[/mathjaxinline]new state [mathjaxinline]\rangle[/mathjaxinline].</span></p>
</blockquote>
<p><span style="font-family: book antiqua,palatino;">The parameters of a command line are to be filled in as follows:</span></p>
<ul>
<li><span style="font-family: book antiqua,palatino;">[mathjaxinline]\langle[/mathjaxinline]current state [mathjaxinline]\rangle[/mathjaxinline] and [mathjaxinline]\langle [/mathjaxinline] new state [mathjaxinline]\rangle[/mathjaxinline] are filled with numerals (“0”, “1”, “2”, etc.).</span></li>
<li><span style="font-family: book antiqua,palatino;">[mathjaxinline]\langle[/mathjaxinline] current symbol [mathjaxinline]\rangle[/mathjaxinline] and [mathjaxinline]\langle[/mathjaxinline]new symbol [mathjaxinline]\rangle[/mathjaxinline] can be filled with letters or numerals (e.g. “[mathjaxinline]a[/mathjaxinline]”, “0”), or with the special symbol </span><span style="font-family: book antiqua,palatino;"><span style="font-family: 'book antiqua', palatino;">“</span>_”, which is used to indicate a blank.</span></li>
<li><span style="font-family: book antiqua,palatino;">[mathjaxinline]\langle[/mathjaxinline] direction [mathjaxinline]\rangle[/mathjaxinline] are filled with “l” (for “left), “r” (for “right”), or “[mathjaxinline]*[/mathjaxinline]" (for “don’t move”).</span></li>
</ul>
<p><span style="font-family: book antiqua,palatino;">For instance, the command line “[mathjaxinline]7 \ 0 \ 1 \ r \ 2[/mathjaxinline]</span><span style="font-family: book antiqua,palatino;"><span style="font-family: 'book antiqua', palatino;">“</span> is interpreted as the following instruction:</span></p>
<blockquote>
<p><span style="font-family: book antiqua,palatino;">If you are in state 7 and your reader sees “0” written on the memory tape, replace the “0” with a “1”. Then move one step to the right, and go to state 2.</span></p>
</blockquote>
<p><span style="font-family: book antiqua,palatino;">And the command line </span><span style="font-family: book antiqua,palatino;"><span style="font-family: 'book antiqua', palatino;">“</span>[mathjaxinline]0 \ \_ \ a \ * \ 10[/mathjaxinline]” is interpreted as:</span></p>
<blockquote>
<p><span style="font-family: book antiqua,palatino;">If you are in state 0 and your reader sees a blank, replace the blank with an </span><span style="font-family: book antiqua,palatino;"><span style="font-family: 'book antiqua', palatino;">“</span>[mathjaxinline]a[/mathjaxinline]</span><span style="font-family: book antiqua,palatino;"><span style="font-family: 'book antiqua', palatino;">“</span>. Then stay put, but go to state 10.</span></p>
</blockquote>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-graded="False" data-init="VerticalStudentView" data-has-score="False" data-block-type="vertical" data-course-id="course-v1:MITx+24.118x+2T2020" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@7b89aa5d4c154b5a891d8fc86b5cb2e3" data-request-token="f97aa7d65ad011efb7210affdd549e9b" data-runtime-class="LmsRuntime" data-runtime-version="1">
<h2 class="hd hd-2 unit-title">The Turing Machine's Operation</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@e96ae49e107d4b39969b5534a1bf7a9d">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-graded="False" data-init="XBlockToXModuleShim" data-has-score="False" data-block-type="html" data-course-id="course-v1:MITx+24.118x+2T2020" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@e96ae49e107d4b39969b5534a1bf7a9d" data-request-token="f97aa7d65ad011efb7210affdd549e9b" data-runtime-class="LmsRuntime" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;"> A Turing Machine always starts out in state 0, and runs in stages. At each stage, the machine performs the instruction corresponding to the command line that matches its current state and the symbol on which its reader is positioned. (Or the first such command line, if there is more than one.) Then it goes on to the next stage. If at any stage the machine is unable to find a command line that matches its present state and the symbol on which its reader is positioned, the machine halts. (To make Turing Machine programs easier for humans to understand, programmers sometimes use “halt” as a name for a non-existing state.) </span></p>
<h4><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">An Example</span></h4>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">Consider the Turing Machine whose program consists of the following commands: </span></p>
<center>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">[mathjaxinline] \begin{array}{ccccc} 0 &\_ &k &* &1\\ 0 &a &o &r &0 \end{array} [/mathjaxinline] </span></p>
</center>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">As always, our machine starts out in state 0. We’ll suppose, moreover, that its tape and reader have been initialized as follows:</span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;"><img src="https://studio.edx.org/asset-v1:MITx+24.118x+1T2018+type@asset+block@FiguresDiagramsParadoxInfinity-21final3.png" alt="" width="1053" height="345" type="saveimage" target="[object Object]" preventdefault="function (){r.isDefaultPrevented=n}" stoppropagation="function (){r.isPropagationStopped=n}" stopimmediatepropagation="function (){r.isImmediatePropagationStopped=n}" isdefaultprevented="function t(){return!1}" ispropagationstopped="function t(){return!1}" isimmediatepropagationstopped="function t(){return!1}" /></span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">(I subscript the arrow with "[mathjaxinline]s=0[/mathjaxinline]" to indicate that the Turing Machine is in state 0 at the time depicted by the diagram.) This is what happens when the Turing Machine is set in motion:</span></p>
<p style="padding-left: 30px;"><span style="font-family: 'book antiqua', palatino;"><strong> Step 1</strong></span><br /><span style="font-family: 'book antiqua', palatino;">The machine starts out in state 0 and its reader sees "[mathjaxinline]a[/mathjaxinline]". So the machine will look for a command line starting with [mathjaxinline]0 \ a[/mathjaxinline] (or the first such command line, if there is more than one). It finds [mathjaxinline]0 \ a \ o \ r \ 0[/mathjaxinline], and follows that instruction by replacing the [mathjaxinline]a[/mathjaxinline] with an [mathjaxinline]o[/mathjaxinline], moving its reader one cell to the right, and remaining in state 0:</span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;"><img src="https://studio.edx.org/asset-v1:MITx+24.118x+1T2018+type@asset+block@FiguresDiagramsParadoxInfinity-22.png" alt="" width="1217" height="311" type="saveimage" target="[object Object]" preventdefault="function (){r.isDefaultPrevented=n}" stoppropagation="function (){r.isPropagationStopped=n}" stopimmediatepropagation="function (){r.isImmediatePropagationStopped=n}" isdefaultprevented="function t(){return!1}" ispropagationstopped="function t(){return!1}" isimmediatepropagationstopped="function t(){return!1}" /></span></p>
<p style="padding-left: 30px;"><span style="font-family: 'book antiqua', palatino;"><strong>Step 2</strong></span><br /><span style="font-family: 'book antiqua', palatino;">The machine is still in state 0 but is now reading a blank. So it looks for a command line starting with [mathjaxinline]0 \ \_[/mathjaxinline] (or the first such command line, if there is more than one). It finds [mathjaxinline]0 \ \_ \ k \ * \ 1[/mathjaxinline] and follows that instruction by replacing the blank with a [mathjaxinline]k[/mathjaxinline], remaining in its current position, and switching to state 1:</span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;"><img src="https://studio.edx.org/asset-v1:MITx+24.118x+1T2018+type@asset+block@FiguresDiagramsParadoxInfinity-22final.png" alt="" width="1074" height="275" type="saveimage" target="[object Object]" preventdefault="function (){r.isDefaultPrevented=n}" stoppropagation="function (){r.isPropagationStopped=n}" stopimmediatepropagation="function (){r.isImmediatePropagationStopped=n}" isdefaultprevented="function t(){return!1}" ispropagationstopped="function t(){return!1}" isimmediatepropagationstopped="function t(){return!1}" /></span></p>
<p style="padding-left: 30px;"><span style="font-family: 'book antiqua', palatino;"><strong>Step 3</strong></span><br /><span style="font-family: 'book antiqua', palatino;">The machine is now in state 1, reading a [mathjaxinline]k[/mathjaxinline]. It has no command line that starts with "1 [mathjaxinline]k[/mathjaxinline]", so it halts.</span></p>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+24.118x+2T2020+type@video+block@8833155c00e2466dbe05000b6a758e77">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-graded="False" data-init="XBlockToXModuleShim" data-has-score="False" data-block-type="video" data-course-id="course-v1:MITx+24.118x+2T2020" data-usage-id="block-v1:MITx+24.118x+2T2020+type@video+block@8833155c00e2466dbe05000b6a758e77" data-request-token="f97aa7d65ad011efb7210affdd549e9b" data-runtime-class="LmsRuntime" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video Review: Turing Machines</h3>
<div
id="video_8833155c00e2466dbe05000b6a758e77"
class="video closed"
data-metadata='{"saveStateEnabled": false, "publishCompletionUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@8833155c00e2466dbe05000b6a758e77/handler/publish_completion", "end": 0.0, "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@8833155c00e2466dbe05000b6a758e77/handler/transcript/available_translations", "autohideHtml5": false, "autoAdvance": false, "speed": null, "completionEnabled": false, "prioritizeHls": false, "transcriptLanguage": "en", "ytMetadataEndpoint": "", "completionPercentage": 0.95, "showCaptions": "true", "captionDataDir": null, "generalSpeed": 1.0, "lmsRootURL": "https://openlearninglibrary.mit.edu", "ytApiUrl": "https://www.youtube.com/iframe_api", "sources": [], "transcriptTranslationUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@8833155c00e2466dbe05000b6a758e77/handler/transcript/translation/__lang__", "poster": null, "recordedYoutubeIsAvailable": true, "ytTestTimeout": 1500, "transcriptLanguages": {"en": "English"}, "streams": "1.00:wSbXxsWO25o", "savedVideoPosition": 0.0, "duration": 0.0, "saveStateUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@8833155c00e2466dbe05000b6a758e77/handler/xmodule_handler/save_user_state", "start": 0.0, "autoplay": false}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="8833155c00e2466dbe05000b6a758e77"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
<h3 class="hd hd-4 downloads-heading sr" id="video-download-transcripts_8833155c00e2466dbe05000b6a758e77">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_8833155c00e2466dbe05000b6a758e77">
<div class="wrapper-download-transcripts">
<h4 class="hd hd-5">Transcripts</h4>
<ul class="list-download-transcripts">
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@8833155c00e2466dbe05000b6a758e77/handler/transcript/download" data-value="srt">Download SubRip (.srt) file</a>
</li>
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@8833155c00e2466dbe05000b6a758e77/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
<div class="vert vert-2" data-id="block-v1:MITx+24.118x+2T2020+type@video+block@c8bed3d28548477fa1cd1e6336e60015">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-graded="False" data-init="XBlockToXModuleShim" data-has-score="False" data-block-type="video" data-course-id="course-v1:MITx+24.118x+2T2020" data-usage-id="block-v1:MITx+24.118x+2T2020+type@video+block@c8bed3d28548477fa1cd1e6336e60015" data-request-token="f97aa7d65ad011efb7210affdd549e9b" data-runtime-class="LmsRuntime" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Coding A Turing Machine</h3>
<div
id="video_c8bed3d28548477fa1cd1e6336e60015"
class="video closed"
data-metadata='{"saveStateEnabled": false, "publishCompletionUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@c8bed3d28548477fa1cd1e6336e60015/handler/publish_completion", "end": 0.0, "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@c8bed3d28548477fa1cd1e6336e60015/handler/transcript/available_translations", "autohideHtml5": false, "autoAdvance": false, "speed": null, "completionEnabled": false, "prioritizeHls": false, "transcriptLanguage": "en", "ytMetadataEndpoint": "", "completionPercentage": 0.95, "showCaptions": "true", "captionDataDir": null, "generalSpeed": 1.0, "lmsRootURL": "https://openlearninglibrary.mit.edu", "ytApiUrl": "https://www.youtube.com/iframe_api", "sources": [], "transcriptTranslationUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@c8bed3d28548477fa1cd1e6336e60015/handler/transcript/translation/__lang__", "poster": null, "recordedYoutubeIsAvailable": true, "ytTestTimeout": 1500, "transcriptLanguages": {"en": "English"}, "streams": "1.00:mcAwQNBJ9nI", "savedVideoPosition": 0.0, "duration": 0.0, "saveStateUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@c8bed3d28548477fa1cd1e6336e60015/handler/xmodule_handler/save_user_state", "start": 0.0, "autoplay": false}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="c8bed3d28548477fa1cd1e6336e60015"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
<h3 class="hd hd-4 downloads-heading sr" id="video-download-transcripts_c8bed3d28548477fa1cd1e6336e60015">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_c8bed3d28548477fa1cd1e6336e60015">
<div class="wrapper-download-transcripts">
<h4 class="hd hd-5">Transcripts</h4>
<ul class="list-download-transcripts">
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@c8bed3d28548477fa1cd1e6336e60015/handler/transcript/download" data-value="srt">Download SubRip (.srt) file</a>
</li>
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@c8bed3d28548477fa1cd1e6336e60015/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
<div class="vert vert-3" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@8c97baf752514d55aa47f23ed0c56243">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-graded="False" data-init="XBlockToXModuleShim" data-has-score="False" data-block-type="html" data-course-id="course-v1:MITx+24.118x+2T2020" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@8c97baf752514d55aa47f23ed0c56243" data-request-token="f97aa7d65ad011efb7210affdd549e9b" data-runtime-class="LmsRuntime" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p><span style="font-family: 'book antiqua', palatino;">In working through the exercises below, I recommend working with a Turing Machine simulator. There are several good simulators online, but you might find the one at <a href="http://morphett.info/turing/turing.html" class="uri">http://morphett.info/turing/turing.html</a> especially helpful, since it uses the same notation as this book.</span></p>
<p></p>
</div>
</div>
<div class="vert vert-4" data-id="block-v1:MITx+24.118x+2T2020+type@problem+block@82645b8951014faaaa91c162272ebb16">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-graded="False" data-init="XBlockToXModuleShim" data-has-score="True" data-block-type="problem" data-course-id="course-v1:MITx+24.118x+2T2020" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@82645b8951014faaaa91c162272ebb16" data-request-token="f97aa7d65ad011efb7210affdd549e9b" data-runtime-class="LmsRuntime" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_82645b8951014faaaa91c162272ebb16" class="problems-wrapper" role="group"
aria-labelledby="82645b8951014faaaa91c162272ebb16-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@82645b8951014faaaa91c162272ebb16" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@82645b8951014faaaa91c162272ebb16/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="82645b8951014faaaa91c162272ebb16-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@82645b8951014faaaa91c162272ebb16-problem-progress" tabindex="-1">
Problem 1
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@82645b8951014faaaa91c162272ebb16-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><p>
<span style="font-family: 'book antiqua', palatino;">Assume a blank tape. Which of the following Turing Machine programs writes "1" on two consecutive cells and then halts?</span>
</p>
<div class="choicegroup capa_inputtype" id="inputtype_82645b8951014faaaa91c162272ebb16_2_1">
<fieldset aria-describedby="status_82645b8951014faaaa91c162272ebb16_2_1">
<div class="field">
<input type="radio" name="input_82645b8951014faaaa91c162272ebb16_2_1" id="input_82645b8951014faaaa91c162272ebb16_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="82645b8951014faaaa91c162272ebb16_2_1-choice_0-label" for="input_82645b8951014faaaa91c162272ebb16_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_82645b8951014faaaa91c162272ebb16_2_1">
<span style="font-family: 'book antiqua', palatino;">
<span class="math display">\[\begin{array}{ccccc}
0 &amp;\_ &amp;1 &amp;* &amp;1\\
1 &amp; 1 &amp;1 &amp;r &amp;\text{halt}
\end{array}\]</span>
</span>
</label>
</div>
<div class="field">
<input type="radio" name="input_82645b8951014faaaa91c162272ebb16_2_1" id="input_82645b8951014faaaa91c162272ebb16_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="82645b8951014faaaa91c162272ebb16_2_1-choice_1-label" for="input_82645b8951014faaaa91c162272ebb16_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_82645b8951014faaaa91c162272ebb16_2_1">
<span style="font-family: 'book antiqua', palatino;">
<span class="math display">\[\begin{array}{ccccc}
0 &amp;\_ &amp;1 &amp;r &amp;1\\
1 &amp;\_ &amp;1 &amp;* &amp;\text{halt}
\end{array}\]</span>
</span>
</label>
</div>
<div class="field">
<input type="radio" name="input_82645b8951014faaaa91c162272ebb16_2_1" id="input_82645b8951014faaaa91c162272ebb16_2_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="82645b8951014faaaa91c162272ebb16_2_1-choice_2-label" for="input_82645b8951014faaaa91c162272ebb16_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_82645b8951014faaaa91c162272ebb16_2_1">
<span style="font-family: 'book antiqua', palatino;">
<span class="math display">\[\begin{array}{ccccc}
0 &amp;\_ &amp;1 &amp;r &amp;0\\
1 &amp; \_ &amp;1 &amp;* &amp;\text{halt}
\end{array}\]</span>
</span>
</label>
</div>
<span id="answer_82645b8951014faaaa91c162272ebb16_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_82645b8951014faaaa91c162272ebb16_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div><div class="solution-span">
<span id="solution_82645b8951014faaaa91c162272ebb16_solution_1"/>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Problem 1" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_82645b8951014faaaa91c162272ebb16" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_82645b8951014faaaa91c162272ebb16">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="82645b8951014faaaa91c162272ebb16-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="82645b8951014faaaa91c162272ebb16-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="82645b8951014faaaa91c162272ebb16-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-5" data-id="block-v1:MITx+24.118x+2T2020+type@problem+block@46182aa9c5f84fc5bb0359757717eb7d">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-graded="False" data-init="XBlockToXModuleShim" data-has-score="True" data-block-type="problem" data-course-id="course-v1:MITx+24.118x+2T2020" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@46182aa9c5f84fc5bb0359757717eb7d" data-request-token="f97aa7d65ad011efb7210affdd549e9b" data-runtime-class="LmsRuntime" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_46182aa9c5f84fc5bb0359757717eb7d" class="problems-wrapper" role="group"
aria-labelledby="46182aa9c5f84fc5bb0359757717eb7d-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@46182aa9c5f84fc5bb0359757717eb7d" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@46182aa9c5f84fc5bb0359757717eb7d/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="46182aa9c5f84fc5bb0359757717eb7d-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@46182aa9c5f84fc5bb0359757717eb7d-problem-progress" tabindex="-1">
Problem 2
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@46182aa9c5f84fc5bb0359757717eb7d-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><p>
<span style="font-family: 'book antiqua', palatino;">Assume a tape that consists of a finite sequence of zeroes and ones surrounded by blanks, and a reader positioned at left-most member of the sequence. Which of the following Turing Machine programs replaces the zeroes with ones, the ones with zeroes, and then halts?</span>
</p>
<div class="choicegroup capa_inputtype" id="inputtype_46182aa9c5f84fc5bb0359757717eb7d_2_1">
<fieldset aria-describedby="status_46182aa9c5f84fc5bb0359757717eb7d_2_1">
<div class="field">
<input type="radio" name="input_46182aa9c5f84fc5bb0359757717eb7d_2_1" id="input_46182aa9c5f84fc5bb0359757717eb7d_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="46182aa9c5f84fc5bb0359757717eb7d_2_1-choice_0-label" for="input_46182aa9c5f84fc5bb0359757717eb7d_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_46182aa9c5f84fc5bb0359757717eb7d_2_1">
<span style="font-family: 'book antiqua', palatino;">
<span class="math display">\[\begin{array}{ccccc}
0 &amp;0 &amp;1 &amp;r &amp;0 \\
0 &amp;1 &amp;0 &amp;r &amp;1\\
1 &amp;\_ &amp;\_ &amp;* &amp;\text{halt}
\end{array}\]</span>
</span>
</label>
</div>
<div class="field">
<input type="radio" name="input_46182aa9c5f84fc5bb0359757717eb7d_2_1" id="input_46182aa9c5f84fc5bb0359757717eb7d_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="46182aa9c5f84fc5bb0359757717eb7d_2_1-choice_1-label" for="input_46182aa9c5f84fc5bb0359757717eb7d_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_46182aa9c5f84fc5bb0359757717eb7d_2_1">
<span style="font-family: 'book antiqua', palatino;">
<span class="math display">\[\begin{array}{ccccc}
0 &amp;0 &amp;1 &amp;r &amp;1 \\
1 &amp;1 &amp;0 &amp;r &amp;2\\
2 &amp;\_ &amp;\_ &amp;* &amp;\text{halt}
\end{array}\]</span>
</span>
</label>
</div>
<div class="field">
<input type="radio" name="input_46182aa9c5f84fc5bb0359757717eb7d_2_1" id="input_46182aa9c5f84fc5bb0359757717eb7d_2_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="46182aa9c5f84fc5bb0359757717eb7d_2_1-choice_2-label" for="input_46182aa9c5f84fc5bb0359757717eb7d_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_46182aa9c5f84fc5bb0359757717eb7d_2_1">
<span style="font-family: 'book antiqua', palatino;">
<span class="math display">\[\begin{array}{ccccc}
0 &amp;0 &amp;1 &amp;r &amp;0 \\
0 &amp;1 &amp;0 &amp;r &amp;0\\
0 &amp;\_ &amp;\_ &amp;* &amp;\text{halt}
\end{array}\]</span>
</span>
</label>
</div>
<span id="answer_46182aa9c5f84fc5bb0359757717eb7d_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_46182aa9c5f84fc5bb0359757717eb7d_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div><div class="solution-span">
<span id="solution_46182aa9c5f84fc5bb0359757717eb7d_solution_1"/>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Problem 2" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_46182aa9c5f84fc5bb0359757717eb7d" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_46182aa9c5f84fc5bb0359757717eb7d">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="46182aa9c5f84fc5bb0359757717eb7d-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="46182aa9c5f84fc5bb0359757717eb7d-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="46182aa9c5f84fc5bb0359757717eb7d-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-6" data-id="block-v1:MITx+24.118x+2T2020+type@problem+block@530539f5c03242b38a36ab994e54f90f">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-graded="False" data-init="XBlockToXModuleShim" data-has-score="True" data-block-type="problem" data-course-id="course-v1:MITx+24.118x+2T2020" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@530539f5c03242b38a36ab994e54f90f" data-request-token="f97aa7d65ad011efb7210affdd549e9b" data-runtime-class="LmsRuntime" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_530539f5c03242b38a36ab994e54f90f" class="problems-wrapper" role="group"
aria-labelledby="530539f5c03242b38a36ab994e54f90f-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@530539f5c03242b38a36ab994e54f90f" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@530539f5c03242b38a36ab994e54f90f/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="530539f5c03242b38a36ab994e54f90f-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@530539f5c03242b38a36ab994e54f90f-problem-progress" tabindex="-1">
Problem 3
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@530539f5c03242b38a36ab994e54f90f-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><p>
<span style="font-family: 'book antiqua', palatino;">Assume a tape that contains a sequence of <span class="math display">\(n\)</span> ones (<span class="math display">\(n &gt; 0\)</span>) and is otherwise blank. Assume a reader positioned at the left-most member of the sequence. Which of the following Turing Machine programs doubles the length of the string of ones, and halts with the reader at the left-most one?</span>
</p>
<div class="choicegroup capa_inputtype" id="inputtype_530539f5c03242b38a36ab994e54f90f_2_1">
<fieldset aria-describedby="status_530539f5c03242b38a36ab994e54f90f_2_1">
<div class="field">
<input type="radio" name="input_530539f5c03242b38a36ab994e54f90f_2_1" id="input_530539f5c03242b38a36ab994e54f90f_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="530539f5c03242b38a36ab994e54f90f_2_1-choice_0-label" for="input_530539f5c03242b38a36ab994e54f90f_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_530539f5c03242b38a36ab994e54f90f_2_1">
<span style="font-family: 'book antiqua', palatino;">
<span class="math display">\[\begin{array}{ccccc}
0 &amp;1 &amp;\_ &amp;r &amp;1\\
1 &amp;1 &amp;1 &amp;r &amp;1\\
1 &amp;\_ &amp;\_ &amp;r &amp;2\\
2 &amp;1 &amp;1 &amp;r &amp;2\\
2 &amp;\_ &amp;1 &amp;r &amp;3\\
3 &amp;\_ &amp;1 &amp;l &amp;4\\
4 &amp;1 &amp;1 &amp;l &amp;4\\
4 &amp;\_ &amp;\_ &amp;l &amp;5\\
5 &amp;1 &amp;1 &amp;l &amp;5\\
5 &amp;\_ &amp;\_ &amp;r &amp;6\\
6 &amp;1 &amp;\_ &amp;r &amp;1\\
6 &amp;\_ &amp;\_ &amp;r &amp;\text{halt}
\end{array}\]</span>
</span>
</label>
</div>
<div class="field">
<input type="radio" name="input_530539f5c03242b38a36ab994e54f90f_2_1" id="input_530539f5c03242b38a36ab994e54f90f_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="530539f5c03242b38a36ab994e54f90f_2_1-choice_1-label" for="input_530539f5c03242b38a36ab994e54f90f_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_530539f5c03242b38a36ab994e54f90f_2_1">
<span style="font-family: 'book antiqua', palatino;">
<span class="math display">\[\begin{array}{ccccc}
0 &amp;1 &amp;\_ &amp;r &amp;0\\
0 &amp;1 &amp;1 &amp;r &amp;1\\
1 &amp;\_ &amp;\_ &amp;r &amp;2\\
2 &amp;1 &amp;1 &amp;r &amp;2\\
2 &amp;\_ &amp;1 &amp;r &amp;3\\
3 &amp;\_ &amp;1 &amp;l &amp;4\\
4 &amp;1 &amp;1 &amp;l &amp;4\\
4 &amp;\_ &amp;\_ &amp;l &amp;5\\
5 &amp;1 &amp;1 &amp;l &amp;5\\
5 &amp;\_ &amp;\_ &amp;r &amp;6\\
6 &amp;1 &amp;\_ &amp;r &amp;1\\
6 &amp;\_ &amp;\_ &amp;r &amp;\text{halt}
\end{array}\]</span>
</span>
</label>
</div>
<span id="answer_530539f5c03242b38a36ab994e54f90f_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_530539f5c03242b38a36ab994e54f90f_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div><div class="solution-span">
<span id="solution_530539f5c03242b38a36ab994e54f90f_solution_1"/>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Problem 3" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_530539f5c03242b38a36ab994e54f90f" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_530539f5c03242b38a36ab994e54f90f">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="530539f5c03242b38a36ab994e54f90f-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="530539f5c03242b38a36ab994e54f90f-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="530539f5c03242b38a36ab994e54f90f-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-7" data-id="block-v1:MITx+24.118x+2T2020+type@problem+block@12d56dd656464618839d36f9ff386edb">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-graded="False" data-init="XBlockToXModuleShim" data-has-score="True" data-block-type="problem" data-course-id="course-v1:MITx+24.118x+2T2020" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@12d56dd656464618839d36f9ff386edb" data-request-token="f97aa7d65ad011efb7210affdd549e9b" data-runtime-class="LmsRuntime" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_12d56dd656464618839d36f9ff386edb" class="problems-wrapper" role="group"
aria-labelledby="12d56dd656464618839d36f9ff386edb-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@12d56dd656464618839d36f9ff386edb" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@12d56dd656464618839d36f9ff386edb/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="12d56dd656464618839d36f9ff386edb-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@12d56dd656464618839d36f9ff386edb-problem-progress" tabindex="-1">
Problem 4
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@12d56dd656464618839d36f9ff386edb-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><p>
<span style="font-family: 'book antiqua', palatino;">Assume a tape that contains a sequence of <span class="math display">\(n\)</span> ones (<span class="math display">\(n &gt; 0\)</span>) and is otherwise blank. Assume a reader positioned at the left-most member of the sequence. Which of the following Turing Machine programs replaces the sequence of <span class="math display">\(n\)</span> ones with a sequence of zeroes and ones that names <span class="math display">\(n\)</span> in binary notation?</span>
</p>
<div class="choicegroup capa_inputtype" id="inputtype_12d56dd656464618839d36f9ff386edb_2_1">
<fieldset aria-describedby="status_12d56dd656464618839d36f9ff386edb_2_1">
<div class="field">
<input type="radio" name="input_12d56dd656464618839d36f9ff386edb_2_1" id="input_12d56dd656464618839d36f9ff386edb_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="12d56dd656464618839d36f9ff386edb_2_1-choice_0-label" for="input_12d56dd656464618839d36f9ff386edb_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_12d56dd656464618839d36f9ff386edb_2_1">
<span style="font-family: 'book antiqua', palatino;">
<span class="math display">\[\begin{array}{ccccc}
0 &amp;1 &amp;1 &amp;r &amp;0\\
0 &amp;\_ &amp;\_ &amp;l &amp;1\\
1 &amp;1 &amp;\_ &amp;l &amp;2\\
1 &amp;\_ &amp;\_ &amp;* &amp;0\\
2 &amp;1 &amp;1 &amp;l &amp;2\\
2 &amp;\_ &amp;\_ &amp;l &amp;3\\
3 &amp;\_ &amp;1 &amp;r &amp;4\\
3 &amp;0 &amp;1 &amp;r &amp;4\\
3 &amp;1 &amp;0 &amp;l &amp;3\\
4 &amp;0 &amp;0 &amp;r &amp;4\\
4 &amp;1 &amp;1 &amp;r &amp;4\\
4 &amp;\_ &amp;\_ &amp;r &amp;\text{halt}
\end{array}\]</span>
</span>
</label>
</div>
<div class="field">
<input type="radio" name="input_12d56dd656464618839d36f9ff386edb_2_1" id="input_12d56dd656464618839d36f9ff386edb_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="12d56dd656464618839d36f9ff386edb_2_1-choice_1-label" for="input_12d56dd656464618839d36f9ff386edb_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_12d56dd656464618839d36f9ff386edb_2_1">
<span style="font-family: 'book antiqua', palatino;">
<span class="math display">\[\begin{array}{ccccc}
0 &amp;1 &amp;1 &amp;r &amp;0\\
0 &amp;\_ &amp;\_ &amp;l &amp;1\\
1 &amp;1 &amp;\_ &amp;l &amp;2\\
1 &amp;\_ &amp;\_ &amp;* &amp;\text{halt}\\
2 &amp;1 &amp;1 &amp;l &amp;2\\
2 &amp;\_ &amp;\_ &amp;l &amp;3\\
3 &amp;\_ &amp;1 &amp;r &amp;4\\
3 &amp;0 &amp;1 &amp;r &amp;4\\
3 &amp;1 &amp;0 &amp;l &amp;3\\
4 &amp;0 &amp;0 &amp;r &amp;4\\
4 &amp;1 &amp;1 &amp;r &amp;4\\
4 &amp;\_ &amp;\_ &amp;r &amp;0
\end{array}\]</span>
</span>
</label>
</div>
<span id="answer_12d56dd656464618839d36f9ff386edb_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_12d56dd656464618839d36f9ff386edb_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div><div class="solution-span">
<span id="solution_12d56dd656464618839d36f9ff386edb_solution_1"/>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Problem 4" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_12d56dd656464618839d36f9ff386edb" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_12d56dd656464618839d36f9ff386edb">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="12d56dd656464618839d36f9ff386edb-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="12d56dd656464618839d36f9ff386edb-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="12d56dd656464618839d36f9ff386edb-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-8" data-id="block-v1:MITx+24.118x+2T2020+type@problem+block@9a47bf05abda4c928a793ce0d991f746">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-graded="False" data-init="XBlockToXModuleShim" data-has-score="True" data-block-type="problem" data-course-id="course-v1:MITx+24.118x+2T2020" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@9a47bf05abda4c928a793ce0d991f746" data-request-token="f97aa7d65ad011efb7210affdd549e9b" data-runtime-class="LmsRuntime" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_9a47bf05abda4c928a793ce0d991f746" class="problems-wrapper" role="group"
aria-labelledby="9a47bf05abda4c928a793ce0d991f746-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@9a47bf05abda4c928a793ce0d991f746" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@9a47bf05abda4c928a793ce0d991f746/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="9a47bf05abda4c928a793ce0d991f746-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@9a47bf05abda4c928a793ce0d991f746-problem-progress" tabindex="-1">
Problem 5
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@9a47bf05abda4c928a793ce0d991f746-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><p>
<span style="font-family: 'book antiqua', palatino;">Assume the tape contains a sequence of zeroes and ones and is otherwise blank, with the reader positioned at the left-most member of the sequence. Which of the following Turing Machine programs replaces the original sequence with a sequence of <span class="math display">\(n\)</span> ones, where the original sequence names <span class="math display">\(n\)</span> in binary notation?</span>
</p>
<div class="choicegroup capa_inputtype" id="inputtype_9a47bf05abda4c928a793ce0d991f746_2_1">
<fieldset aria-describedby="status_9a47bf05abda4c928a793ce0d991f746_2_1">
<div class="field">
<input type="radio" name="input_9a47bf05abda4c928a793ce0d991f746_2_1" id="input_9a47bf05abda4c928a793ce0d991f746_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="9a47bf05abda4c928a793ce0d991f746_2_1-choice_0-label" for="input_9a47bf05abda4c928a793ce0d991f746_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_9a47bf05abda4c928a793ce0d991f746_2_1">
<span style="font-family: 'book antiqua', palatino;">
<span class="math display">\[\begin{array}{cccccl}
0 &amp;0 &amp;0 &amp;r &amp;0 &amp;\text{ ; startup}\\
0 &amp;1 &amp;1 &amp;r &amp;0\\
0 &amp;\_ &amp;\_ &amp;l &amp;1\\
1 &amp;1 &amp;0 &amp;r &amp;2 &amp;\text{ ; subtract}\\
1 &amp;0 &amp;1 &amp;l &amp;1\\
1 &amp;\_ &amp;\_ &amp;r &amp;5\\
2 &amp;0 &amp;0 &amp;r &amp;2&amp;\text{ ; move right to add}\\
2 &amp;1 &amp;1 &amp;r &amp;2\\
2 &amp;\_ &amp;\_ &amp;r &amp;3\\
3 &amp;\_ &amp;1 &amp;l &amp;4 &amp;\text{ ; add one}\\
3 &amp;1 &amp;1 &amp;r &amp;3\\
4 &amp;1 &amp;1 &amp;l &amp;4&amp;\text{ ; turn back}\\
4 &amp;\_ &amp;\_ &amp;l &amp;1\\
5 &amp;1 &amp;\_ &amp;r &amp;5 &amp;\text{ ; wrap things up}\\
5 &amp;\_ &amp;\_ &amp;r &amp;\text{halt}
\end{array}\]</span>
</span>
</label>
</div>
<div class="field">
<input type="radio" name="input_9a47bf05abda4c928a793ce0d991f746_2_1" id="input_9a47bf05abda4c928a793ce0d991f746_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="9a47bf05abda4c928a793ce0d991f746_2_1-choice_1-label" for="input_9a47bf05abda4c928a793ce0d991f746_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_9a47bf05abda4c928a793ce0d991f746_2_1">
<span style="font-family: 'book antiqua', palatino;">
<span class="math display">\[\begin{array}{cccccl}
0 &amp;0 &amp;0 &amp;r &amp;0 &amp;\text{ ; startup}\\
0 &amp;1 &amp;1 &amp;r &amp;1\\
0 &amp;\_ &amp;\_ &amp;l &amp;0\\
1 &amp;1 &amp;0 &amp;r &amp;2 &amp;\text{ ; subtract}\\
1 &amp;0 &amp;1 &amp;l &amp;1\\
1 &amp;\_ &amp;\_ &amp;r &amp;5\\
2 &amp;0 &amp;0 &amp;r &amp;2&amp;\text{ ; move right to add}\\
2 &amp;1 &amp;1 &amp;r &amp;2\\
2 &amp;\_ &amp;\_ &amp;r &amp;3\\
3 &amp;\_ &amp;1 &amp;l &amp;4 &amp;\text{ ; add one}\\
3 &amp;1 &amp;1 &amp;r &amp;3\\
4 &amp;1 &amp;1 &amp;l &amp;4&amp;\text{ ; turn back}\\
4 &amp;\_ &amp;\_ &amp;l &amp;1\\
5 &amp;1 &amp;\_ &amp;r &amp;5 &amp;\text{ ; wrap things up}\\
5 &amp;\_ &amp;\_ &amp;r &amp;\text{halt}
\end{array}\]</span>
</span>
</label>
</div>
<span id="answer_9a47bf05abda4c928a793ce0d991f746_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_9a47bf05abda4c928a793ce0d991f746_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div><div class="solution-span">
<span id="solution_9a47bf05abda4c928a793ce0d991f746_solution_1"/>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Problem 5" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_9a47bf05abda4c928a793ce0d991f746" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_9a47bf05abda4c928a793ce0d991f746">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="9a47bf05abda4c928a793ce0d991f746-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="9a47bf05abda4c928a793ce0d991f746-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="9a47bf05abda4c928a793ce0d991f746-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-graded="False" data-init="VerticalStudentView" data-has-score="False" data-block-type="vertical" data-course-id="course-v1:MITx+24.118x+2T2020" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@87d6a89d42684831b43e80491510def2" data-request-token="f97aa7d65ad011efb7210affdd549e9b" data-runtime-class="LmsRuntime" data-runtime-version="1">
<h2 class="hd hd-2 unit-title">Computing functions on a Turing Machine</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@522f093eddc6461f95ddf93784a92e58">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-graded="False" data-init="XBlockToXModuleShim" data-has-score="False" data-block-type="html" data-course-id="course-v1:MITx+24.118x+2T2020" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@522f093eddc6461f95ddf93784a92e58" data-request-token="f97aa7d65ad011efb7210affdd549e9b" data-runtime-class="LmsRuntime" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p><span style="font-family: 'book antiqua', palatino;">Let <span class="math inline">\(f\)</span> be a function from natural numbers to natural numbers. An ordinary computer (running an ordinary computer program) computes <span class="math inline">\(f\)</span> if and only if the following holds for each natural number <span class="math inline">\(n\)</span>:</span></p>
<blockquote>
<p><span style="font-family: 'book antiqua', palatino;">If you give the ordinary computer <span class="math inline">\(n\)</span> as input, you’ll get <span class="math inline">\(f(n)\)</span> as output.</span></p>
</blockquote>
<p><span style="font-family: 'book antiqua', palatino;">Turing Machines can be used to implement a version of this idea. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">For we can think of a Turing Machine as taking number <span class="math inline">\(n\)</span> (<span class="math inline">\(n \geq 0\)</span>) as <strong>input</strong> if it starts out with a tape that contains only a sequence of <span class="math inline">\(n\)</span> ones (with the reader positioned at the left-most one, if <span class="math inline">\(n > 0\)</span>). </span></p>
<p><span style="font-family: 'book antiqua', palatino;">And we can think of the Turing Machine as delivering number <span class="math inline">\(f(n)\)</span> as <strong>output</strong> if it halts with a tape that contains only a sequence of <span class="math inline">\(f(n)\)</span> ones (with the reader positioned at the left-most one, if <span class="math inline">\(f(n) > 0\)</span>). </span></p>
<p><span style="font-family: 'book antiqua', palatino;">Finally, we can say that a Turing Machine <strong>computes</strong> a function <span class="math inline">\(f(x)\)</span> if and only if it it delivers <span class="math inline">\(f(n)\)</span> as output whenever it is given <span class="math inline">\(n\)</span> as input. (For a function to be <strong>Turing-computable</strong> is for it to be computed by some Turing Machine.)</span></p>
<p><span style="font-family: 'book antiqua', palatino;">Notice, incidentally, that a similar definition could be used to define computability for functions from <span class="math inline">\(n\)</span>-tuples of natural numbers to natural numbers. For we can think of a Turing Machine as taking a sequence of natural numbers <span class="math inline">\(\langle n_1,\dots,n_k\rangle\)</span> as <strong>input</strong> if it starts out with a tape that contains only a sequence composed of the following: a sequence of <span class="math inline">\(n_1\)</span> ones (or a blank, if <span class="math inline">\(n_1 =0\)</span>), followed by a blank, followed by a sequence of <span class="math inline">\(n_2\)</span> ones (or a blank, if <span class="math inline">\(n_2 =0\)</span>), followed by a blank, followed by …, followed by a sequence of <span class="math inline">\(n_k\)</span> ones (or a blank, if <span class="math inline">\(n_k =0\)</span>), with the reader positioned at the left-most one of the left-most sequence of ones (unless <span class="math inline">\(n_1 = 0\)</span>, in which case the reader is positioned at the blank corresponding to <span class="math inline">\(n_1\)</span>).</span></p>
<p></p>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+24.118x+2T2020+type@video+block@d9adc357961f4eb3b1dc83c5081a9943">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-graded="False" data-init="XBlockToXModuleShim" data-has-score="False" data-block-type="video" data-course-id="course-v1:MITx+24.118x+2T2020" data-usage-id="block-v1:MITx+24.118x+2T2020+type@video+block@d9adc357961f4eb3b1dc83c5081a9943" data-request-token="f97aa7d65ad011efb7210affdd549e9b" data-runtime-class="LmsRuntime" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video Review: Computing A Function</h3>
<div
id="video_d9adc357961f4eb3b1dc83c5081a9943"
class="video closed"
data-metadata='{"saveStateEnabled": false, "publishCompletionUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@d9adc357961f4eb3b1dc83c5081a9943/handler/publish_completion", "end": 0.0, "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@d9adc357961f4eb3b1dc83c5081a9943/handler/transcript/available_translations", "autohideHtml5": false, "autoAdvance": false, "speed": null, "completionEnabled": false, "prioritizeHls": false, "transcriptLanguage": "en", "ytMetadataEndpoint": "", "completionPercentage": 0.95, "showCaptions": "true", "captionDataDir": null, "generalSpeed": 1.0, "lmsRootURL": "https://openlearninglibrary.mit.edu", "ytApiUrl": "https://www.youtube.com/iframe_api", "sources": [], "transcriptTranslationUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@d9adc357961f4eb3b1dc83c5081a9943/handler/transcript/translation/__lang__", "poster": null, "recordedYoutubeIsAvailable": true, "ytTestTimeout": 1500, "transcriptLanguages": {"en": "English"}, "streams": "1.00:wSbXxsWO25o", "savedVideoPosition": 0.0, "duration": 0.0, "saveStateUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@d9adc357961f4eb3b1dc83c5081a9943/handler/xmodule_handler/save_user_state", "start": 0.0, "autoplay": false}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="d9adc357961f4eb3b1dc83c5081a9943"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
<h3 class="hd hd-4 downloads-heading sr" id="video-download-transcripts_d9adc357961f4eb3b1dc83c5081a9943">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_d9adc357961f4eb3b1dc83c5081a9943">
<div class="wrapper-download-transcripts">
<h4 class="hd hd-5">Transcripts</h4>
<ul class="list-download-transcripts">
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@d9adc357961f4eb3b1dc83c5081a9943/handler/transcript/download" data-value="srt">Download SubRip (.srt) file</a>
</li>
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@d9adc357961f4eb3b1dc83c5081a9943/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-graded="False" data-init="VerticalStudentView" data-has-score="False" data-block-type="vertical" data-course-id="course-v1:MITx+24.118x+2T2020" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@9df9480b15e945b5a4580198aef040c9" data-request-token="f97aa7d65ad011efb7210affdd549e9b" data-runtime-class="LmsRuntime" data-runtime-version="1">
<h2 class="hd hd-2 unit-title">The Fundamental Theorem</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@215cd16dd1e641d2af6245bc83f5630c">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-graded="False" data-init="XBlockToXModuleShim" data-has-score="False" data-block-type="html" data-course-id="course-v1:MITx+24.118x+2T2020" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@215cd16dd1e641d2af6245bc83f5630c" data-request-token="f97aa7d65ad011efb7210affdd549e9b" data-runtime-class="LmsRuntime" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;"> The reason Turing Machines are so incredibly useful is that it is possible to prove the following theorem: </span></p>
<p style="padding-left: 30px;"><span style="font-family: 'book antiqua', palatino;"><strong>Fundamental Theorem of Turing Machines</strong></span><br /><span style="font-family: 'book antiqua', palatino;">A function from natural numbers to natural numbers is Turing-computable if and only if it can be computed by an ordinary computer, given unlimited memory and running time.</span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">(What I mean by “ordinary computer” here is what sometimes gets referred to as a “register machine”, but the details won’t matter for present purposes.) </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">The proof of the Fundamental Theorem is long and clunky, but the basic idea is straightforward: </span></p>
<ul>
<li><span style="font-family: 'book antiqua', palatino;">One shows that every Turing-computable function is computable by an ordinary computer (given unlimited memory and running time) by showing that one can program an ordinary computer to simulate any given Turing Machine.</span></li>
<li><span style="font-family: 'book antiqua', palatino;">One shows that every function computable by an ordinary computer (given unlimited memory and running time) is Turing-computable by showing that one can find a Turing Machine that simulates any given ordinary computer.</span></li>
</ul>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;"> In fact, computer scientists tend to think that something stronger than the Fundamental Theorem is true: </span></p>
<p style="padding-left: 30px;"><span style="font-family: 'book antiqua', palatino;"><strong>Church-Turing Thesis</strong></span><br /><span style="font-family: 'book antiqua', palatino;">A function is Turing-computable if and only if it can be computed algorithmically.</span></p>
<p></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">For a problem to be solvable <strong>algorithmically</strong> is for it to be possible to specify a finite list of instructions for solving the problem such that: </span></p>
<ol>
<li><span style="font-family: 'book antiqua', palatino;">following the instructions is guaranteed to yield a solution to the problem, in a finite amount of time.</span></li>
<li><span style="font-family: 'book antiqua', palatino;">the instructions are specific enough that they could be carried out by a fully autonomous mechanism whose workings we fully understand.</span></li>
</ol>
<p><span style="font-family: 'book antiqua', palatino;">Intuitively speaking, you can think of the Church-Turing Thesis as stating that a function is Turing-computable if and only if there is a <em>finite</em> way of specifying what its values are. So, in particular, a function that fails to be Turing-computable is a function that is so complex that its values cannot be finitely specified.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">I mentioned above that computer scientists tend to think that the Church-Turing Thesis is true. But this is not because they are able to prove it. It’s actually not clear what a formal proof of the Church-Turing Thesis would look like. The problem is that such a proof would require a formal characterization of the notion of an algorithmic computability, and it is not clear that one could formalize the notion of algorithmic computability without thereby restricting its scope. (Notice, for example, that the notion of Turing-computability is itself one natural way of formalizing the notion of algorithmic computability. On such a formalization, the Church-Turing Thesis is certainly true. But it is also trivial.) </span></p>
<p><span style="font-family: 'book antiqua', palatino;">The reason the Church-Turing Thesis is widely regarded as true is that any sensible formalization of the notion of algorithmic computability that anyone has ever been able to come up with is provably equivalent to the notion of Turing-computability.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">Programming with Turing Machines can be somewhat cumbersome. But Turing Machines are so incredibly simple that theorizing about Turing Machines tends to be pretty straightforward. In light of the Fundamental Theorem, this means that theorizing <em>about</em> Turing Machines is an extremely useful way of gaining insight about computers more generally. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">Assuming the Church-Turing Thesis is true, it also means that theorizing about Turing Machines is an extremely useful way of gaining insight about algorithmic methods more generally.</span></p>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+24.118x+2T2020+type@video+block@0219945e108f4cb696321879b66f3584">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-graded="False" data-init="XBlockToXModuleShim" data-has-score="False" data-block-type="video" data-course-id="course-v1:MITx+24.118x+2T2020" data-usage-id="block-v1:MITx+24.118x+2T2020+type@video+block@0219945e108f4cb696321879b66f3584" data-request-token="f97aa7d65ad011efb7210affdd549e9b" data-runtime-class="LmsRuntime" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video Review: Church-Turing Thesis</h3>
<div
id="video_0219945e108f4cb696321879b66f3584"
class="video closed"
data-metadata='{"saveStateEnabled": false, "publishCompletionUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@0219945e108f4cb696321879b66f3584/handler/publish_completion", "end": 0.0, "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@0219945e108f4cb696321879b66f3584/handler/transcript/available_translations", "autohideHtml5": false, "autoAdvance": false, "speed": null, "completionEnabled": false, "prioritizeHls": false, "transcriptLanguage": "en", "ytMetadataEndpoint": "", "completionPercentage": 0.95, "showCaptions": "true", "captionDataDir": null, "generalSpeed": 1.0, "lmsRootURL": "https://openlearninglibrary.mit.edu", "ytApiUrl": "https://www.youtube.com/iframe_api", "sources": [], "transcriptTranslationUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@0219945e108f4cb696321879b66f3584/handler/transcript/translation/__lang__", "poster": null, "recordedYoutubeIsAvailable": true, "ytTestTimeout": 1500, "transcriptLanguages": {"en": "English"}, "streams": "1.00:mDrtOosd3eQ", "savedVideoPosition": 0.0, "duration": 0.0, "saveStateUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@0219945e108f4cb696321879b66f3584/handler/xmodule_handler/save_user_state", "start": 0.0, "autoplay": false}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="0219945e108f4cb696321879b66f3584"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
<h3 class="hd hd-4 downloads-heading sr" id="video-download-transcripts_0219945e108f4cb696321879b66f3584">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_0219945e108f4cb696321879b66f3584">
<div class="wrapper-download-transcripts">
<h4 class="hd hd-5">Transcripts</h4>
<ul class="list-download-transcripts">
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@0219945e108f4cb696321879b66f3584/handler/transcript/download" data-value="srt">Download SubRip (.srt) file</a>
</li>
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@0219945e108f4cb696321879b66f3584/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-graded="False" data-init="VerticalStudentView" data-has-score="False" data-block-type="vertical" data-course-id="course-v1:MITx+24.118x+2T2020" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@6ae42c64326d471cb0899557527829c2" data-request-token="f97aa7d65ad011efb7210affdd549e9b" data-runtime-class="LmsRuntime" data-runtime-version="1">
<h2 class="hd hd-2 unit-title">Numbering Turing Machines</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@45cfc7ff66a84f8fa62e6a2a790044a4">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-graded="False" data-init="XBlockToXModuleShim" data-has-score="False" data-block-type="html" data-course-id="course-v1:MITx+24.118x+2T2020" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@45cfc7ff66a84f8fa62e6a2a790044a4" data-request-token="f97aa7d65ad011efb7210affdd549e9b" data-runtime-class="LmsRuntime" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;"> Turing Machines can be numbered. More specifically: we can <em>code</em> Turing Machines as natural numbers in such a way that no two Turing Machines are assigned the same code. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">In this section I’ll describe one way of doing so. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">Two preliminary observations: </span></p>
<ol>
<li><span style="font-family: 'book antiqua', palatino;">The only differences between Turing Machines that we’ll care about here are differences in their programs. Accordingly, we will only count Turing Machines as different if they instantiate different programs. On the other hand, we will treat Turing Machines as different even if there are differences in their programs that make no difference to their behavior. As long as their programs consist of different lists of symbols, the machines will be counted as distinct.</span></li>
<li><span style="font-family: 'book antiqua', palatino;">I will simplify the discussion by focusing on <strong>one-symbol</strong> Turing Machines, in which the only symbol allowed on the tape (not counting blanks) is “1”. This looks like a substantial assumption, but it’s actually not. As you’ll be asked to verify in one of the exercises below, every function that can be computed on a many-symbol Turing Machine can also be computed on a one-symbol Turing Machine.</span></li>
</ol>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">The coding scheme we will discuss in this section proceeds in stages. First, we’ll code a Turing machine as a sequence of symbols; then we’ll code the sequence of symbols as a sequence of numerals; finally, we’ll code the sequence of numerals as a single number: </span></p>
<center><span style="font-family: 'book antiqua', palatino;">Turing Machine [mathjaxinline]\rightarrow[/mathjaxinline] Sequence of symbols [mathjaxinline]\rightarrow[/mathjaxinline] Sequence of numbers [mathjaxinline]\rightarrow [/mathjaxinline] Unique Number</span></center>
<p></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">Let us consider each stage in turn.</span></p>
<h4><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">Turing Machine [mathjaxinline]\rightarrow[/mathjaxinline]Sequence of symbols </span></h4>
<p><span style="font-family: 'book antiqua', palatino;">Since we are counting Turing Machines with the same program as one and the same, we can think of a Turing Machine program as a sequence of command lines. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">Each command line is a sequence of symbols. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">So all we need to do to encode a Turing Machine as a sequence of symbols is concatenate its commands. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">For instance, the Turing Machine with program:</span></p>
<center>
<p><span style="font-family: 'book antiqua', palatino;">[mathjaxinline] \begin{array}{ccccc} 0 &\_ &1 &* &0\\ 0 &1 &\_ &l &1 \end{array} [/mathjaxinline]</span></p>
</center>
<p><span style="font-family: 'book antiqua', palatino;">gets coded as the sequence of symbols:</span></p>
<center>
<p><span style="font-family: 'book antiqua', palatino;">[mathjaxinline] \begin{array}{cccccccccc} 0 &\_ &1 &* &0 &0 &1 &\_ &l &1 \end{array} [/mathjaxinline]</span></p>
</center>
<h4><span style="font-family: 'book antiqua', palatino;">Sequence of symbols [mathjaxinline]\rightarrow [/mathjaxinline] Sequence of numbers</span></h4>
<p><span style="font-family: 'book antiqua', palatino;">We have managed to code each Turing Machine as a sequence of symbols. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">We will now code each of these symbols as a number. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">Recall that each command line in a Turing Machine program results from filling out the following parameters:</span></p>
<center>
<p><span style="font-family: 'book antiqua', palatino;">[mathjaxinline]\langle[/mathjaxinline]current state [mathjaxinline]\rangle[/mathjaxinline] [mathjaxinline]\langle[/mathjaxinline] current symbol [mathjaxinline]\rangle[/mathjaxinline] [mathjaxinline]\langle[/mathjaxinline]new symbol [mathjaxinline]\rangle[/mathjaxinline] [mathjaxinline]\langle[/mathjaxinline]direction [mathjaxinline]\rangle[/mathjaxinline] [mathjaxinline]\langle[/mathjaxinline]new state [mathjaxinline]\rangle[/mathjaxinline]</span></p>
</center>
<p><span style="font-family: 'book antiqua', palatino;">We will employ the following coding scheme:</span></p>
<ul>
<li><span style="font-family: 'book antiqua', palatino;">[mathjaxinline]\langle[/mathjaxinline] current state [mathjaxinline]\rangle[/mathjaxinline] and [mathjaxinline]\langle[/mathjaxinline] new state [mathjaxinline]\rangle[/mathjaxinline] will always be filled in with numerals (which are names of numbers). So we’ll code each numeral by the number it represents:</span></li>
</ul>
<center>
<p><span class="math display" style="font-family: 'book antiqua', palatino;">\[\begin{array}{ccc} \text{"0"} &\rightarrow &\text{0}\\ \text{"1"} &\rightarrow &\text{1}\\ \vdots &\vdots\\ \end{array}\]</span></p>
</center>
<ul>
<li><span style="font-family: 'book antiqua', palatino;">[mathjaxinline]\langle[/mathjaxinline]current symbol [mathjaxinline]\rangle[/mathjaxinline] and [mathjaxinline]\langle[/mathjaxinline] new symbol [mathjaxinline]\rangle[/mathjaxinline] will always be filled in with “1” or “_ ”. (Recall that we are working with one-symbol Turing Machines.) So we’ll use the following codes:</span></li>
</ul>
<p><span style="font-family: 'book antiqua', palatino;">\begin{array}{ccc} \text{"_"} &\rightarrow &\text{0}\\ \text{"1"} &\rightarrow &\text{1} \end{array} </span></p>
<ul>
<li><span style="font-family: 'book antiqua', palatino;">[mathjaxinline]\langle[/mathjaxinline]direction [mathjaxinline]\rangle[/mathjaxinline] is "r", "[mathjaxinline]*[/mathjaxinline]" or "l". We’ll use the following codes:</span></li>
</ul>
<center><center><span style="font-family: 'book antiqua', palatino;">[mathjaxinline] \begin{array}{ccc} \text{"r''} &\rightarrow &\text{0}\\ \text{"$*$''} &\rightarrow &\text{1}\\ \text{"l''} &\rightarrow &\text{2} \end{array} [/mathjaxinline]</span></center></center>
<p><span style="font-family: 'book antiqua', palatino;">So, for instance, the sequence of symbols</span></p>
<center>
<p><span style="font-family: 'book antiqua', palatino;">[mathjaxinline] \begin{array}{cccccccccc} 0 &\_ &1 &* &0 &0 &1 &\_ &l &1 \end{array} [/mathjaxinline]</span></p>
</center>
<p><span style="font-family: 'book antiqua', palatino;">gets transformed into the sequence of numbers:</span></p>
<center>
<p><span style="font-family: 'book antiqua', palatino;">[mathjaxinline] \begin{array}{cccccccccc} 0 &0 &1 &1 &0 &0 &1 &0 &2 &1 \end{array} [/mathjaxinline]</span></p>
</center>
<h4><span style="font-family: 'book antiqua', palatino;">Sequence of numbers [mathjaxinline]\rightarrow[/mathjaxinline]Unique number</span></h4>
<p><span style="font-family: 'book antiqua', palatino;">The final step in our coding scheme is a method for coding each sequence of numbers as a single natural number. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">There are many ways of doing so, but the method we will consider here is due to the great Austrian logician and philosopher Kurt G¨odel, about whom you’ll be hearing more in the next lecture. It is extremely simple. One simply codes the sequence of numerals [mathjaxinline]\langle[/mathjaxinline] n_1, n_2, [mathjaxinline] \dots [/mathjaxinline], [mathjaxinline] n_k [/mathjaxinline] [mathjaxinline]\rangle[/mathjaxinline] as the number:</span></p>
<p></p>
<center>
<p><span style="font-family: 'book antiqua', palatino;">[mathjaxinline]p_{1}[/mathjaxinline] [mathjaxinline]^{n_{1}+1}[/mathjaxinline] [mathjaxinline]\cdot[/mathjaxinline] [mathjaxinline]p_2[/mathjaxinline] [mathjaxinline]^{n_2+1}[/mathjaxinline] [mathjaxinline]\cdot[/mathjaxinline] [mathjaxinline]\ldots[/mathjaxinline] [mathjaxinline]\cdot [/mathjaxinline] [mathjaxinline]p_k[/mathjaxinline] [mathjaxinline]^{n_k+1}[/mathjaxinline]</span></p>
</center>
<p><span style="font-family: 'book antiqua', palatino;">where [mathjaxinline]p_1[/mathjaxinline] [mathjaxinline]\ldots[/mathjaxinline] [mathjaxinline]p_k[/mathjaxinline] are the first [mathjaxinline]k[/mathjaxinline] prime numbers. (The “empty” Turing Machine, which has no command lines, is coded as the number 1.) </span></p>
<p><span style="font-family: 'book antiqua', palatino;">For instance, the sequence of numbers [mathjaxinline]\langle[/mathjaxinline]0,0,1,2,0 [mathjaxinline]\rangle[/mathjaxinline] gets coded as:</span></p>
<center>
<p><span style="font-family: 'book antiqua', palatino;">[mathjaxinline]2^{0+1}\cdot 3^{0+1}\cdot 5^{1+1}\cdot 7^{2+1}\cdot 11^{0+1} = 2\cdot 3\cdot 25\cdot 343\cdot 11 = 565,950[/mathjaxinline]</span></p>
</center>
<p><span style="font-family: 'book antiqua', palatino;">(Why add one to exponents? Because otherwise our coding scheme would be ambiguous. For instance, it would use 1 as a code for each of the following sequences: [mathjaxinline]\langle[/mathjaxinline]0[mathjaxinline]\rangle[/mathjaxinline], [mathjaxinline]\langle[/mathjaxinline]0,0[mathjaxinline]\rangle[/mathjaxinline], [mathjaxinline]\langle[/mathjaxinline]0,0,0[mathjaxinline]\rangle[/mathjaxinline], etc.)</span></p>
<p><span style="font-family: 'book antiqua', palatino;">To ensure that this coding scheme gives us what we want, we need to verify that different Turing Machines are always assigned different codes. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">Fortunately, this is an immediate consequence of the following:</span></p>
<p style="padding-left: 30px;"><span style="font-family: 'book antiqua', palatino;"><strong>Fundamental Theorem of Arithmetic</strong></span><br /><span style="font-family: 'book antiqua', palatino;">Every positive integer greater than 1 has a unique decomposition into primes.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">We have now done what we set out to do: we have identified a coding-scheme which assigns a different number to each one-symbol Turing Machine.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">Since the discussion below will presuppose that a fixed coding scheme is in place, I hereby stipulate that it is to be the coding scheme described in this section, with one small qualification. Our scheme so far does not associate a Turing Machine with every number, since not every number codes a valid sequence of command lines. This turns out to be a nuisance, so I will stipulate that any number that doesn’t code a valid sequence of command lines is to be treated as a code for the “empty” Turing Machine. The result is a coding scheme on which: ([mathjaxinline]a[/mathjaxinline]) every number codes some Turing Machine, and ([mathjaxinline]b[/mathjaxinline]) every Turing Machine is coded by some number.</span></p>
<p><strong>Warning: </strong>In the video below, we encode "left" as 1 and "stay" as 2, contrary to the encoding described above. You should use the encoding described above, not the encoding in the video, when you do the exercises.</p>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+24.118x+2T2020+type@video+block@1c9d5931ae2949e0843661a234fa4350">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-graded="False" data-init="XBlockToXModuleShim" data-has-score="False" data-block-type="video" data-course-id="course-v1:MITx+24.118x+2T2020" data-usage-id="block-v1:MITx+24.118x+2T2020+type@video+block@1c9d5931ae2949e0843661a234fa4350" data-request-token="f97aa7d65ad011efb7210affdd549e9b" data-runtime-class="LmsRuntime" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video Review: Numbering Turing Machines</h3>
<div
id="video_1c9d5931ae2949e0843661a234fa4350"
class="video closed"
data-metadata='{"saveStateEnabled": false, "publishCompletionUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@1c9d5931ae2949e0843661a234fa4350/handler/publish_completion", "end": 0.0, "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@1c9d5931ae2949e0843661a234fa4350/handler/transcript/available_translations", "autohideHtml5": false, "autoAdvance": false, "speed": null, "completionEnabled": false, "prioritizeHls": false, "transcriptLanguage": "en", "ytMetadataEndpoint": "", "completionPercentage": 0.95, "showCaptions": "true", "captionDataDir": null, "generalSpeed": 1.0, "lmsRootURL": "https://openlearninglibrary.mit.edu", "ytApiUrl": "https://www.youtube.com/iframe_api", "sources": [], "transcriptTranslationUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@1c9d5931ae2949e0843661a234fa4350/handler/transcript/translation/__lang__", "poster": null, "recordedYoutubeIsAvailable": true, "ytTestTimeout": 1500, "transcriptLanguages": {"en": "English"}, "streams": "1.00:8q2LAmk8dWk", "savedVideoPosition": 0.0, "duration": 0.0, "saveStateUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@1c9d5931ae2949e0843661a234fa4350/handler/xmodule_handler/save_user_state", "start": 0.0, "autoplay": false}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="1c9d5931ae2949e0843661a234fa4350"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
<h3 class="hd hd-4 downloads-heading sr" id="video-download-transcripts_1c9d5931ae2949e0843661a234fa4350">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_1c9d5931ae2949e0843661a234fa4350">
<div class="wrapper-download-transcripts">
<h4 class="hd hd-5">Transcripts</h4>
<ul class="list-download-transcripts">
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@1c9d5931ae2949e0843661a234fa4350/handler/transcript/download" data-value="srt">Download SubRip (.srt) file</a>
</li>
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@1c9d5931ae2949e0843661a234fa4350/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
<div class="vert vert-2" data-id="block-v1:MITx+24.118x+2T2020+type@problem+block@bb3e19d3f5864e2dbe38978235f0c1da">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-graded="False" data-init="XBlockToXModuleShim" data-has-score="True" data-block-type="problem" data-course-id="course-v1:MITx+24.118x+2T2020" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@bb3e19d3f5864e2dbe38978235f0c1da" data-request-token="f97aa7d65ad011efb7210affdd549e9b" data-runtime-class="LmsRuntime" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_bb3e19d3f5864e2dbe38978235f0c1da" class="problems-wrapper" role="group"
aria-labelledby="bb3e19d3f5864e2dbe38978235f0c1da-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@bb3e19d3f5864e2dbe38978235f0c1da" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@bb3e19d3f5864e2dbe38978235f0c1da/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="bb3e19d3f5864e2dbe38978235f0c1da-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@bb3e19d3f5864e2dbe38978235f0c1da-problem-progress" tabindex="-1">
Problem 1
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@bb3e19d3f5864e2dbe38978235f0c1da-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><p>
<span style="font-family: 'book antiqua', palatino;">On the coding system above, what number gets assigned to the Turing Machine whose program consists of the following command line?</span>
</p>
<p>
<span style="font-family: 'book antiqua', palatino;">
<span class="math display">\[\begin{array}{ccccc}
0 &amp;1 &amp;\_ &amp;* &amp;1
\end{array}\]</span>
</span>
</p>
<div id="formulaequationinput_bb3e19d3f5864e2dbe38978235f0c1da_2_1" class="inputtype formulaequationinput">
<div class="unanswered">
<input type="text" name="input_bb3e19d3f5864e2dbe38978235f0c1da_2_1" id="input_bb3e19d3f5864e2dbe38978235f0c1da_2_1" data-input-id="bb3e19d3f5864e2dbe38978235f0c1da_2_1" value="" aria-describedby="status_bb3e19d3f5864e2dbe38978235f0c1da_2_1" size="20"/>
<span class="trailing_text" id="trailing_text_bb3e19d3f5864e2dbe38978235f0c1da_2_1"/>
<span class="status unanswered" id="status_bb3e19d3f5864e2dbe38978235f0c1da_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_bb3e19d3f5864e2dbe38978235f0c1da_2_1" class="answer"/>
<div id="input_bb3e19d3f5864e2dbe38978235f0c1da_2_1_preview" class="equation">
\(\)
<img src="/static/images/spinner.bc34f953403f.gif" class="loading" alt="Loading"/>
</div>
</div>
<div class="script_placeholder" data-src="/static/js/capa/src/formula_equation_preview.b1967ab28c31.js"/>
</div><div class="solution-span">
<span id="solution_bb3e19d3f5864e2dbe38978235f0c1da_solution_1"/>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Problem 1" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_bb3e19d3f5864e2dbe38978235f0c1da" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_bb3e19d3f5864e2dbe38978235f0c1da">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="bb3e19d3f5864e2dbe38978235f0c1da-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="bb3e19d3f5864e2dbe38978235f0c1da-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="bb3e19d3f5864e2dbe38978235f0c1da-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-3" data-id="block-v1:MITx+24.118x+2T2020+type@problem+block@9e6f20106d0b49f2ba0ee8c582f33d72">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-graded="False" data-init="XBlockToXModuleShim" data-has-score="True" data-block-type="problem" data-course-id="course-v1:MITx+24.118x+2T2020" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@9e6f20106d0b49f2ba0ee8c582f33d72" data-request-token="f97aa7d65ad011efb7210affdd549e9b" data-runtime-class="LmsRuntime" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_9e6f20106d0b49f2ba0ee8c582f33d72" class="problems-wrapper" role="group"
aria-labelledby="9e6f20106d0b49f2ba0ee8c582f33d72-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@9e6f20106d0b49f2ba0ee8c582f33d72" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@9e6f20106d0b49f2ba0ee8c582f33d72/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="9e6f20106d0b49f2ba0ee8c582f33d72-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@9e6f20106d0b49f2ba0ee8c582f33d72-problem-progress" tabindex="-1">
Problem 2
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@9e6f20106d0b49f2ba0ee8c582f33d72-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><p>
<span style="font-family: 'book antiqua', palatino;">Using the coding system above, which of the following programs corresponds to Turing Machine number 97,020?</span>
</p>
<div class="choicegroup capa_inputtype" id="inputtype_9e6f20106d0b49f2ba0ee8c582f33d72_2_1">
<fieldset aria-describedby="status_9e6f20106d0b49f2ba0ee8c582f33d72_2_1">
<div class="field">
<input type="radio" name="input_9e6f20106d0b49f2ba0ee8c582f33d72_2_1" id="input_9e6f20106d0b49f2ba0ee8c582f33d72_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="9e6f20106d0b49f2ba0ee8c582f33d72_2_1-choice_0-label" for="input_9e6f20106d0b49f2ba0ee8c582f33d72_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_9e6f20106d0b49f2ba0ee8c582f33d72_2_1">
<span style="font-family: 'book antiqua', palatino;">
<span class="math display">\[\begin{array}{ccccc}
1 &amp;1 &amp;1 &amp;* &amp;0
\end{array}\]</span>
</span>
</label>
</div>
<div class="field">
<input type="radio" name="input_9e6f20106d0b49f2ba0ee8c582f33d72_2_1" id="input_9e6f20106d0b49f2ba0ee8c582f33d72_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="9e6f20106d0b49f2ba0ee8c582f33d72_2_1-choice_1-label" for="input_9e6f20106d0b49f2ba0ee8c582f33d72_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_9e6f20106d0b49f2ba0ee8c582f33d72_2_1">
<span style="font-family: 'book antiqua', palatino;">
<span class="math display">\[\begin{array}{ccccc}
1 &amp;1 &amp;\_ &amp;* &amp;0
\end{array}\]</span>
</span>
</label>
</div>
<div class="field">
<input type="radio" name="input_9e6f20106d0b49f2ba0ee8c582f33d72_2_1" id="input_9e6f20106d0b49f2ba0ee8c582f33d72_2_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="9e6f20106d0b49f2ba0ee8c582f33d72_2_1-choice_2-label" for="input_9e6f20106d0b49f2ba0ee8c582f33d72_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_9e6f20106d0b49f2ba0ee8c582f33d72_2_1">
<span style="font-family: 'book antiqua', palatino;">
<span class="math display">\[\begin{array}{ccccc}
1 &amp;\_ &amp;1 &amp;* &amp;0
\end{array}\]</span>
</span>
</label>
</div>
<span id="answer_9e6f20106d0b49f2ba0ee8c582f33d72_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_9e6f20106d0b49f2ba0ee8c582f33d72_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div><div class="solution-span">
<span id="solution_9e6f20106d0b49f2ba0ee8c582f33d72_solution_1"/>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Problem 2" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_9e6f20106d0b49f2ba0ee8c582f33d72" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_9e6f20106d0b49f2ba0ee8c582f33d72">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="9e6f20106d0b49f2ba0ee8c582f33d72-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="9e6f20106d0b49f2ba0ee8c582f33d72-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="9e6f20106d0b49f2ba0ee8c582f33d72-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-4" data-id="block-v1:MITx+24.118x+2T2020+type@problem+block@767253a280924a20a31a7b5fad18e98c">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-graded="False" data-init="XBlockToXModuleShim" data-has-score="True" data-block-type="problem" data-course-id="course-v1:MITx+24.118x+2T2020" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@767253a280924a20a31a7b5fad18e98c" data-request-token="f97aa7d65ad011efb7210affdd549e9b" data-runtime-class="LmsRuntime" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_767253a280924a20a31a7b5fad18e98c" class="problems-wrapper" role="group"
aria-labelledby="767253a280924a20a31a7b5fad18e98c-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@767253a280924a20a31a7b5fad18e98c" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@767253a280924a20a31a7b5fad18e98c/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="767253a280924a20a31a7b5fad18e98c-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@767253a280924a20a31a7b5fad18e98c-problem-progress" tabindex="-1">
Problem 3
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@767253a280924a20a31a7b5fad18e98c-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><p>
<span style="font-family: 'book antiqua', palatino;">Show that every function that can be computed on an <span class="math inline">\(n\)</span>-symbol Turing Machine can also be computed on a one-symbol Turing Machine (which is only allowed ones and blanks on the tape).</span>
</p>
<div class="choicegroup capa_inputtype" id="inputtype_767253a280924a20a31a7b5fad18e98c_2_1">
<fieldset aria-describedby="status_767253a280924a20a31a7b5fad18e98c_2_1">
<div class="field">
<input type="checkbox" name="input_767253a280924a20a31a7b5fad18e98c_2_1[]" id="input_767253a280924a20a31a7b5fad18e98c_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="767253a280924a20a31a7b5fad18e98c_2_1-choice_0-label" for="input_767253a280924a20a31a7b5fad18e98c_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_767253a280924a20a31a7b5fad18e98c_2_1">
<span style="font-family: 'book antiqua', palatino;">Done</span>
</label>
</div>
<span id="answer_767253a280924a20a31a7b5fad18e98c_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_767253a280924a20a31a7b5fad18e98c_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div><div class="solution-span">
<span id="solution_767253a280924a20a31a7b5fad18e98c_solution_1"/>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Problem 3" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_767253a280924a20a31a7b5fad18e98c" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_767253a280924a20a31a7b5fad18e98c">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="767253a280924a20a31a7b5fad18e98c-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="767253a280924a20a31a7b5fad18e98c-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="767253a280924a20a31a7b5fad18e98c-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-5" data-id="block-v1:MITx+24.118x+2T2020+type@problem+block@1b1312571eab4d6590185d9027a80337">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-graded="False" data-init="XBlockToXModuleShim" data-has-score="True" data-block-type="problem" data-course-id="course-v1:MITx+24.118x+2T2020" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@1b1312571eab4d6590185d9027a80337" data-request-token="f97aa7d65ad011efb7210affdd549e9b" data-runtime-class="LmsRuntime" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_1b1312571eab4d6590185d9027a80337" class="problems-wrapper" role="group"
aria-labelledby="1b1312571eab4d6590185d9027a80337-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@1b1312571eab4d6590185d9027a80337" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@1b1312571eab4d6590185d9027a80337/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="1b1312571eab4d6590185d9027a80337-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@1b1312571eab4d6590185d9027a80337-problem-progress" tabindex="-1">
Problem 4
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@1b1312571eab4d6590185d9027a80337-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><p>
<span style="font-family: 'book antiqua', palatino;">As it turns out, every function that can be computed on a Turing Machine whose tape is infinite in both directions can also be computed on a Turing Machine whose tape is infinite in only one direction.</span>
</p>
<p>
<span style="font-family: 'book antiqua', palatino;">Suppose that <span class="math inline">\(M^{\infty^2}\)</span> is a Turing Machine that computes function <span class="math inline">\(f(n)\)</span>. Sketch a procedure for transforming <span class="math inline">\(M^{\infty^2}\)</span>&#8217;s into a Turing Machine <span class="math inline">\(M^{\infty}\)</span> that computes <span class="math inline">\(f(n)\)</span> while using a tape that is infinite only in one direction.</span>
</p>
<div class="choicegroup capa_inputtype" id="inputtype_1b1312571eab4d6590185d9027a80337_2_1">
<fieldset aria-describedby="status_1b1312571eab4d6590185d9027a80337_2_1">
<div class="field">
<input type="checkbox" name="input_1b1312571eab4d6590185d9027a80337_2_1[]" id="input_1b1312571eab4d6590185d9027a80337_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="1b1312571eab4d6590185d9027a80337_2_1-choice_0-label" for="input_1b1312571eab4d6590185d9027a80337_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_1b1312571eab4d6590185d9027a80337_2_1">
<span style="font-family: 'book antiqua', palatino;">Done</span>
</label>
</div>
<span id="answer_1b1312571eab4d6590185d9027a80337_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_1b1312571eab4d6590185d9027a80337_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div><div class="solution-span">
<span id="solution_1b1312571eab4d6590185d9027a80337_solution_1"/>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Problem 4" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_1b1312571eab4d6590185d9027a80337" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_1b1312571eab4d6590185d9027a80337">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="1b1312571eab4d6590185d9027a80337-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="1b1312571eab4d6590185d9027a80337-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="1b1312571eab4d6590185d9027a80337-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
© All Rights Reserved