<div class="xblock xblock-public_view xblock-public_view-vertical" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@aee95a36338a46b5a08a0f5b91f2926e" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="vertical" data-request-token="49ee766cfe9111ee8e37026cc65ec0d9" data-has-score="False" data-runtime-version="1" data-init="VerticalStudentView">
<h2 class="hd hd-2 unit-title">Non-computable functions</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@64c111cf62a14f3cb5bebf761bb259b6">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@64c111cf62a14f3cb5bebf761bb259b6" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="html" data-request-token="49ee766cfe9111ee8e37026cc65ec0d9" data-has-score="False" data-runtime-version="1" data-init="XBlockToXModuleShim">
<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;"> Can every function from natural numbers to natural numbers be computed by a Turing Machine? </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">Turing proved that the answer to this question is a resounding “No”. (Assuming the Church-Turing Thesis, you can think of this result as showing that some functions are so complex that their values cannot be finitely specified.) </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">The easiest way to see this is to note that there are more functions from natural numbers to natural numbers than there are Turing Machines. (<em>Proof</em>: in showing that each Turing Machine can be coded by a different natural number, we showed that there are no more Turing Machines than there are natural numbers. And as you were asked to show in Lecture 1, there are more functions from natural numbers to natural numbers than there are natural numbers.) </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">In this lecture I'll give you a couple of examples of functions that are not Turing-computable.</span></p>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+24.118x+2T2020+type@video+block@00bc6551e77143e39c2ae06ac71fc1fd">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-usage-id="block-v1:MITx+24.118x+2T2020+type@video+block@00bc6551e77143e39c2ae06ac71fc1fd" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="video" data-request-token="49ee766cfe9111ee8e37026cc65ec0d9" data-has-score="False" data-runtime-version="1" data-init="XBlockToXModuleShim">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video Review: A Quick Proof There are Non-Computable Fuctions</h3>
<div
id="video_00bc6551e77143e39c2ae06ac71fc1fd"
class="video closed"
data-metadata='{"end": 0.0, "speed": null, "ytTestTimeout": 1500, "publishCompletionUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@00bc6551e77143e39c2ae06ac71fc1fd/handler/publish_completion", "ytApiUrl": "https://www.youtube.com/iframe_api", "showCaptions": "true", "streams": "1.00:VVxWblgmrm4", "poster": null, "saveStateEnabled": false, "start": 0.0, "completionPercentage": 0.95, "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@00bc6551e77143e39c2ae06ac71fc1fd/handler/transcript/available_translations", "autoplay": false, "transcriptLanguages": {"en": "English"}, "autohideHtml5": false, "transcriptTranslationUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@00bc6551e77143e39c2ae06ac71fc1fd/handler/transcript/translation/__lang__", "ytMetadataEndpoint": "", "generalSpeed": 1.0, "lmsRootURL": "https://openlearninglibrary.mit.edu", "autoAdvance": false, "completionEnabled": false, "savedVideoPosition": 0.0, "saveStateUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@00bc6551e77143e39c2ae06ac71fc1fd/handler/xmodule_handler/save_user_state", "captionDataDir": null, "sources": [], "transcriptLanguage": "en", "recordedYoutubeIsAvailable": true, "prioritizeHls": false, "duration": 0.0}'
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="00bc6551e77143e39c2ae06ac71fc1fd"></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_00bc6551e77143e39c2ae06ac71fc1fd">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_00bc6551e77143e39c2ae06ac71fc1fd">
<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@00bc6551e77143e39c2ae06ac71fc1fd/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@00bc6551e77143e39c2ae06ac71fc1fd/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-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@53c499c319d34536a63c779e37b86f29" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="vertical" data-request-token="49ee766cfe9111ee8e37026cc65ec0d9" data-has-score="False" data-runtime-version="1" data-init="VerticalStudentView">
<h2 class="hd hd-2 unit-title">The Halting Function</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@b756742a33364a80b75a5ef996edfdeb">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@b756742a33364a80b75a5ef996edfdeb" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="html" data-request-token="49ee766cfe9111ee8e37026cc65ec0d9" data-has-score="False" data-runtime-version="1" data-init="XBlockToXModuleShim">
<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;"> The most famous example of a function that is not Turing-computable is the <strong>Halting Function.</strong> There are actually two different versions of the Halting Function. </span></span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;"><span style="font-size: 12pt;">The first, [mathjaxinline]H(n,m)[/mathjaxinline], is a function from pairs of natural numbers to natural numbers, and is defined as follows:</span></span></p>
<p><span class="math display" style="font-family: 'book antiqua', palatino;">\[H(n,m) = \begin{cases} 1 \text{ if the \(n\)th Turning Machine halts when given input \(m\);}\\ 0 \text{ otherwise.} \end{cases}\]</span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;"><span style="font-size: 12pt;">Consider, for example, the Turing Machine whose program is the following:</span></span></p>
<p><span class="math display" style="font-family: 'book antiqua', palatino;">\[\begin{array}{ccccc} 0 &\_ &\_ &r &0\end{array}\]</span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;"><span style="font-size: 12pt;">This is the 2310th Turing Machine according to our scheme, because:</span></span></p>
<center><span style="font-family: 'book antiqua', palatino;">[mathjaxinline]2^{0+1}\cdot 3^{0+1}\cdot 5^{0+1}\cdot 7^{0+1}\cdot 11^{0+1} = 2\cdot 3\cdot 5\cdot 7\cdot 11 = 2310[/mathjaxinline]</span></center>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">When given input 0 (i.e. the empty string), this machine will start moving to the right and never stop. So the the 2310th Turing Machine does not halt on input 0. So ([mathjaxinline]H[/mathjaxinline] 2310, 0) = 0. In contrast, when given input [mathjaxinline]n[/mathjaxinline]([mathjaxinline]n>0[/mathjaxinline]), our Turing Machine halts immediately, since it has no command line telling it what to do when reading a “1” in state 0. This means, in particular, that it halts given input 2310. So [mathjaxinline]H[/mathjaxinline](2310. 2310) = 1. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">The second version of the Halting Function, [mathjaxinline]H(n)[/mathjaxinline], is a function from natural numbers to natural numbers. It is defined on the basis of the first version of the Halting Function: </span></p>
<center><span style="font-family: 'book antiqua', palatino;">[mathjaxinline]H(n) = H(n,n)[/mathjaxinline]</span></center><center><span style="font-family: 'book antiqua', palatino;"></span></center>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">So, for example, [mathjaxinline]H[/mathjaxinline](2310) = 1, since we have seen that </span><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">[mathjaxinline]H[/mathjaxinline](2310. 2310) = 1.</span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">In what follows we’ll verify that [mathjaxinline]H(n)[/mathjaxinline] is not Turing-computable. (As you’ll be asked to verify in an exercise below, this entails that [mathjaxinline]H(n,m)[/mathjaxinline] is not Turing-computable either.) These results are due to Alan Turing.</span></p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@cf88beab7dda4dd38c3669a02ee4a761" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="vertical" data-request-token="49ee766cfe9111ee8e37026cc65ec0d9" data-has-score="False" data-runtime-version="1" data-init="VerticalStudentView">
<h2 class="hd hd-2 unit-title">The Proof</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@65f5604fd3324674b096f03f82e8211d">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@65f5604fd3324674b096f03f82e8211d" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="html" data-request-token="49ee766cfe9111ee8e37026cc65ec0d9" data-has-score="False" data-runtime-version="1" data-init="XBlockToXModuleShim">
<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;"> We'll proceed by <em>reductio</em>. More specifically, we’ll assume that there is a Turing Machine [mathjaxinline]M^{H}[/mathjaxinline] that computes [mathjaxinline](H(n)[/mathjaxinline], and show that that would allow us to construct an “impossible” Turing Machine [mathjaxinline]M^I[/mathjaxinline]. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">Here is how to build [mathjaxinline]M^I[/mathjaxinline], on the assumption that [mathjaxinline]M^{H}[/mathjaxinline] exists: </span></p>
<blockquote>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">When [mathjaxinline]M^I[/mathjaxinline] is given input [mathjaxinline]k[/mathjaxinline], it starts by using [mathjaxinline]M^H[/mathjaxinline]'s program as a subroutine to check whether Turing Machine [mathjaxinline]k[/mathjaxinline] halts on input [mathjaxinline]k[/mathjaxinline]. If [mathjaxinline]M^I[/mathjaxinline] gets the answer “yes” (i.e., if its readers is on a “1” after performing the subroutine), then [mathjaxinline]M^I[/mathjaxinline] goes on an infinite loop. Otherwise, it halts. </span></p>
</blockquote>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">But now suppose that [mathjaxinline]M^I[/mathjaxinline] is the [mathjaxinline]i[/mathjaxinline]th Turing Machine, and consider the question of whether [mathjaxinline]M^I[/mathjaxinline] halts given input [mathjaxinline]i[/mathjaxinline]. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">There are two possibilities:</span></p>
<p style="padding-left: 30px;"><span style="font-family: 'book antiqua', palatino;"><strong> [mathjaxinline]M^I[/mathjaxinline] halts on input [mathjaxinline]i[/mathjaxinline]</strong></span><br /><span style="font-family: 'book antiqua', palatino;">By the definition of the Halting Function this means that [mathjaxinline]H(i)=1[/mathjaxinline]. So it follows from the definition of [mathjaxinline]M^I[/mathjaxinline] that [mathjaxinline]M^I[/mathjaxinline] will go on an infinite loop, given input [mathjaxinline]i[/mathjaxinline].</span></p>
<p style="padding-left: 30px;"><span style="font-family: 'book antiqua', palatino;"><strong> [mathjaxinline]M^I[/mathjaxinline] doesn’t halt on input [mathjaxinline]i[/mathjaxinline]</strong></span><br /><span style="font-family: 'book antiqua', palatino;">By the definition of the Halting Function, this means that [mathjaxinline]H(i)=0[/mathjaxinline]. So it follows from the definition of [mathjaxinline]M^I[/mathjaxinline] that [mathjaxinline]M^I[/mathjaxinline] will halt, given input [mathjaxinline]i[/mathjaxinline].</span></p>
<p></p>
<p><span style="font-family: 'book antiqua', palatino;">So [mathjaxinline]M^I[/mathjaxinline] halts if and only if it doesn’t halt, which is impossible. This means that [mathjaxinline]M^I [/mathjaxinline] can’t really exist. So [mathjaxinline]M^H[/mathjaxinline] can’t really exist. So the Halting Function isn’t Turing-computable.</span></p>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+24.118x+2T2020+type@video+block@5ba511f075cf414aaa9e8d333009af91">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-usage-id="block-v1:MITx+24.118x+2T2020+type@video+block@5ba511f075cf414aaa9e8d333009af91" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="video" data-request-token="49ee766cfe9111ee8e37026cc65ec0d9" data-has-score="False" data-runtime-version="1" data-init="XBlockToXModuleShim">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video Review: The Halting Function is Not Computable</h3>
<div
id="video_5ba511f075cf414aaa9e8d333009af91"
class="video closed"
data-metadata='{"end": 0.0, "speed": null, "ytTestTimeout": 1500, "publishCompletionUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@5ba511f075cf414aaa9e8d333009af91/handler/publish_completion", "ytApiUrl": "https://www.youtube.com/iframe_api", "showCaptions": "true", "streams": "1.00:5eYIs_LyWXc", "poster": null, "saveStateEnabled": false, "start": 0.0, "completionPercentage": 0.95, "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@5ba511f075cf414aaa9e8d333009af91/handler/transcript/available_translations", "autoplay": false, "transcriptLanguages": {"en": "English"}, "autohideHtml5": false, "transcriptTranslationUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@5ba511f075cf414aaa9e8d333009af91/handler/transcript/translation/__lang__", "ytMetadataEndpoint": "", "generalSpeed": 1.0, "lmsRootURL": "https://openlearninglibrary.mit.edu", "autoAdvance": false, "completionEnabled": false, "savedVideoPosition": 0.0, "saveStateUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@5ba511f075cf414aaa9e8d333009af91/handler/xmodule_handler/save_user_state", "captionDataDir": null, "sources": [], "transcriptLanguage": "en", "recordedYoutubeIsAvailable": true, "prioritizeHls": false, "duration": 0.0}'
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="5ba511f075cf414aaa9e8d333009af91"></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_5ba511f075cf414aaa9e8d333009af91">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_5ba511f075cf414aaa9e8d333009af91">
<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@5ba511f075cf414aaa9e8d333009af91/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@5ba511f075cf414aaa9e8d333009af91/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@82cc5434e1b94b5caf8b28acada3af74">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@82cc5434e1b94b5caf8b28acada3af74" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="problem" data-request-token="49ee766cfe9111ee8e37026cc65ec0d9" data-has-score="True" data-runtime-version="1" data-init="XBlockToXModuleShim">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_82cc5434e1b94b5caf8b28acada3af74" class="problems-wrapper" role="group"
aria-labelledby="82cc5434e1b94b5caf8b28acada3af74-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@82cc5434e1b94b5caf8b28acada3af74" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@82cc5434e1b94b5caf8b28acada3af74/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="82cc5434e1b94b5caf8b28acada3af74-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@82cc5434e1b94b5caf8b28acada3af74-problem-progress" tabindex="-1">
Problem 1
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@82cc5434e1b94b5caf8b28acada3af74-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;">Our construction of <span class="math inline">\(M^I\)</span> assumes that Turing Machines are able to carry out certain operations.</span>
</p>
<p>
<span style="font-family: 'book antiqua', palatino;">To verify that these assumptions are correct, which of the following is a Turing Machine, <span class="math inline">\(M\)</span>, that behaves as follows: given 1 as input, <span class="math inline">\(M\)</span> goes off on an infinite loop; given a blank as input, <span class="math inline">\(M\)</span> halts?</span>
</p>
<div class="choicegroup capa_inputtype" id="inputtype_82cc5434e1b94b5caf8b28acada3af74_2_1">
<fieldset aria-describedby="status_82cc5434e1b94b5caf8b28acada3af74_2_1">
<div class="field">
<input type="radio" name="input_82cc5434e1b94b5caf8b28acada3af74_2_1" id="input_82cc5434e1b94b5caf8b28acada3af74_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="82cc5434e1b94b5caf8b28acada3af74_2_1-choice_0-label" for="input_82cc5434e1b94b5caf8b28acada3af74_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_82cc5434e1b94b5caf8b28acada3af74_2_1">
<span style="font-family: 'book antiqua', palatino;">
<span class="math display">\[\begin{array}{ccccc}
0 &amp;1 &amp;\_ &amp;* &amp;\text{halt}\\
0 &amp;\_ &amp;1 &amp;* &amp;0
\end{array}\]</span>
</span>
</label>
</div>
<div class="field">
<input type="radio" name="input_82cc5434e1b94b5caf8b28acada3af74_2_1" id="input_82cc5434e1b94b5caf8b28acada3af74_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="82cc5434e1b94b5caf8b28acada3af74_2_1-choice_1-label" for="input_82cc5434e1b94b5caf8b28acada3af74_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_82cc5434e1b94b5caf8b28acada3af74_2_1">
<span style="font-family: 'book antiqua', palatino;">
<span class="math display">\[\begin{array}{ccccc}
0 &amp;\_ &amp;\_ &amp;* &amp;\text{halt}\\
0 &amp;1 &amp;1 &amp;* &amp;0
\end{array}\]</span>
</span>
</label>
</div>
<div class="field">
<input type="radio" name="input_82cc5434e1b94b5caf8b28acada3af74_2_1" id="input_82cc5434e1b94b5caf8b28acada3af74_2_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="82cc5434e1b94b5caf8b28acada3af74_2_1-choice_2-label" for="input_82cc5434e1b94b5caf8b28acada3af74_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_82cc5434e1b94b5caf8b28acada3af74_2_1">
<span style="font-family: 'book antiqua', palatino;">
<span class="math display">\[\begin{array}{ccccc}
0 &amp;\_ &amp;\_ &amp;* &amp;\text{halt}\\
0 &amp;1 &amp;\_ &amp;* &amp;0
\end{array}\]</span>
</span>
</label>
</div>
<span id="answer_82cc5434e1b94b5caf8b28acada3af74_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_82cc5434e1b94b5caf8b28acada3af74_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_82cc5434e1b94b5caf8b28acada3af74_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_82cc5434e1b94b5caf8b28acada3af74" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_82cc5434e1b94b5caf8b28acada3af74">
<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="82cc5434e1b94b5caf8b28acada3af74-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="82cc5434e1b94b5caf8b28acada3af74-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="82cc5434e1b94b5caf8b28acada3af74-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@0eaf02e7b8db4fb984918615d482cf77">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@0eaf02e7b8db4fb984918615d482cf77" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="problem" data-request-token="49ee766cfe9111ee8e37026cc65ec0d9" data-has-score="True" data-runtime-version="1" data-init="XBlockToXModuleShim">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_0eaf02e7b8db4fb984918615d482cf77" class="problems-wrapper" role="group"
aria-labelledby="0eaf02e7b8db4fb984918615d482cf77-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@0eaf02e7b8db4fb984918615d482cf77" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@0eaf02e7b8db4fb984918615d482cf77/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="0eaf02e7b8db4fb984918615d482cf77-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@0eaf02e7b8db4fb984918615d482cf77-problem-progress" tabindex="-1">
Problem 2
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@0eaf02e7b8db4fb984918615d482cf77-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 <span class="math inline">\(H(n,m)\)</span> is not Turing-computable, by showing that if it were Turing-computable, then <span class="math inline">\(H(n)\)</span> would be Turing-computable too.</span>
</p>
<div class="choicegroup capa_inputtype" id="inputtype_0eaf02e7b8db4fb984918615d482cf77_2_1">
<fieldset aria-describedby="status_0eaf02e7b8db4fb984918615d482cf77_2_1">
<div class="field">
<input type="checkbox" name="input_0eaf02e7b8db4fb984918615d482cf77_2_1[]" id="input_0eaf02e7b8db4fb984918615d482cf77_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="0eaf02e7b8db4fb984918615d482cf77_2_1-choice_0-label" for="input_0eaf02e7b8db4fb984918615d482cf77_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_0eaf02e7b8db4fb984918615d482cf77_2_1">
<span style="font-family: 'book antiqua', palatino;">Done</span>
</label>
</div>
<span id="answer_0eaf02e7b8db4fb984918615d482cf77_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_0eaf02e7b8db4fb984918615d482cf77_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_0eaf02e7b8db4fb984918615d482cf77_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_0eaf02e7b8db4fb984918615d482cf77" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_0eaf02e7b8db4fb984918615d482cf77">
<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="0eaf02e7b8db4fb984918615d482cf77-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="0eaf02e7b8db4fb984918615d482cf77-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="0eaf02e7b8db4fb984918615d482cf77-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@e43c28202c9c4facacbf8185c5c14bf9">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@e43c28202c9c4facacbf8185c5c14bf9" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="problem" data-request-token="49ee766cfe9111ee8e37026cc65ec0d9" data-has-score="True" data-runtime-version="1" data-init="XBlockToXModuleShim">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_e43c28202c9c4facacbf8185c5c14bf9" class="problems-wrapper" role="group"
aria-labelledby="e43c28202c9c4facacbf8185c5c14bf9-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@e43c28202c9c4facacbf8185c5c14bf9" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@e43c28202c9c4facacbf8185c5c14bf9/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="e43c28202c9c4facacbf8185c5c14bf9-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@e43c28202c9c4facacbf8185c5c14bf9-problem-progress" tabindex="-1">
Problem 3
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@e43c28202c9c4facacbf8185c5c14bf9-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, there is a <strong>Universal Turing Machine</strong>, <span class="math inline">\(M^U\)</span>, which does the following:</span>
</p>
<ul>
<li>
<p>
<span style="font-family: 'book antiqua', palatino;">if the <span class="math inline">\(m\)</span>th Turing Machine halts given input <span class="math inline">\(n\)</span>, leaving the tape in configuration <span class="math inline">\(p\)</span>, then <span class="math inline">\(M^U\)</span> halts given input <span class="math inline">\(\langle m,n\rangle \)</span> leaving the tape in configuration <span class="math inline">\(p\)</span>.</span>
</p>
</li>
<li>
<p>
<span style="font-family: 'book antiqua', palatino;">if the <span class="math inline">\(m\)</span>th Turing Machine never halts given input <span class="math inline">\(n\)</span>, then <span class="math inline">\(M^U\)</span> never halts given input <span class="math inline">\(\langle m,n\rangle \)</span>.</span>
</p>
</li>
</ul>
<p>
<span style="font-family: 'book antiqua', palatino;">Give an informal description of how a Universal Turing Machine might be implemented. (<em>Hint</em>: when <span class="math inline">\(M^U\)</span> is given <span class="math inline">\(\langle m,n\rangle \)</span> as input it uses its tape to create a simulation of the behavior of Turing Machine <span class="math inline">\(m\)</span> on input <span class="math inline">\(n\)</span>.)</span>
</p>
<div class="choicegroup capa_inputtype" id="inputtype_e43c28202c9c4facacbf8185c5c14bf9_2_1">
<fieldset aria-describedby="status_e43c28202c9c4facacbf8185c5c14bf9_2_1">
<div class="field">
<input type="checkbox" name="input_e43c28202c9c4facacbf8185c5c14bf9_2_1[]" id="input_e43c28202c9c4facacbf8185c5c14bf9_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="e43c28202c9c4facacbf8185c5c14bf9_2_1-choice_0-label" for="input_e43c28202c9c4facacbf8185c5c14bf9_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_e43c28202c9c4facacbf8185c5c14bf9_2_1">
<span style="font-family: 'book antiqua', palatino;">Done</span>
</label>
</div>
<span id="answer_e43c28202c9c4facacbf8185c5c14bf9_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_e43c28202c9c4facacbf8185c5c14bf9_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_e43c28202c9c4facacbf8185c5c14bf9_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_e43c28202c9c4facacbf8185c5c14bf9" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_e43c28202c9c4facacbf8185c5c14bf9">
<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="e43c28202c9c4facacbf8185c5c14bf9-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="e43c28202c9c4facacbf8185c5c14bf9-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="e43c28202c9c4facacbf8185c5c14bf9-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@8a936069904a441f9579a363f6a45fc1">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@8a936069904a441f9579a363f6a45fc1" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="problem" data-request-token="49ee766cfe9111ee8e37026cc65ec0d9" data-has-score="True" data-runtime-version="1" data-init="XBlockToXModuleShim">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_8a936069904a441f9579a363f6a45fc1" class="problems-wrapper" role="group"
aria-labelledby="8a936069904a441f9579a363f6a45fc1-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@8a936069904a441f9579a363f6a45fc1" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@8a936069904a441f9579a363f6a45fc1/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="8a936069904a441f9579a363f6a45fc1-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@8a936069904a441f9579a363f6a45fc1-problem-progress" tabindex="-1">
Problem 4
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@8a936069904a441f9579a363f6a45fc1-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;">Could a Universal Turing Machine be used to compute the Halting Function?</span>
</p>
<p>
<span style="font-family: 'book antiqua', palatino;">More specifically: Could we construct a Turing Machine that does the following, given input <span class="math inline">\(n\)</span>? First, our machine uses the Universal Turing Machine as a subroutine, to figure out what Turing Machine <span class="math inline">\(n\)</span> would do on an empty input. Our machine then prints out a one or a zero, depending on whether the simulation halts.</span>
</p>
<div class="choicegroup capa_inputtype" id="inputtype_8a936069904a441f9579a363f6a45fc1_2_1">
<fieldset aria-describedby="status_8a936069904a441f9579a363f6a45fc1_2_1">
<div class="field">
<input type="radio" name="input_8a936069904a441f9579a363f6a45fc1_2_1" id="input_8a936069904a441f9579a363f6a45fc1_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="8a936069904a441f9579a363f6a45fc1_2_1-choice_0-label" for="input_8a936069904a441f9579a363f6a45fc1_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_8a936069904a441f9579a363f6a45fc1_2_1">
<span style="font-family: 'book antiqua', palatino;">Yes</span>
</label>
</div>
<div class="field">
<input type="radio" name="input_8a936069904a441f9579a363f6a45fc1_2_1" id="input_8a936069904a441f9579a363f6a45fc1_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="8a936069904a441f9579a363f6a45fc1_2_1-choice_1-label" for="input_8a936069904a441f9579a363f6a45fc1_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_8a936069904a441f9579a363f6a45fc1_2_1">
<span style="font-family: 'book antiqua', palatino;">No</span>
</label>
</div>
<span id="answer_8a936069904a441f9579a363f6a45fc1_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_8a936069904a441f9579a363f6a45fc1_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_8a936069904a441f9579a363f6a45fc1_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_8a936069904a441f9579a363f6a45fc1" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_8a936069904a441f9579a363f6a45fc1">
<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="8a936069904a441f9579a363f6a45fc1-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="8a936069904a441f9579a363f6a45fc1-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="8a936069904a441f9579a363f6a45fc1-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@video+block@20f7e79d2987426da34b93e632b52610">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-usage-id="block-v1:MITx+24.118x+2T2020+type@video+block@20f7e79d2987426da34b93e632b52610" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="video" data-request-token="49ee766cfe9111ee8e37026cc65ec0d9" data-has-score="False" data-runtime-version="1" data-init="XBlockToXModuleShim">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video Review: The Universal Turing Machine</h3>
<div
id="video_20f7e79d2987426da34b93e632b52610"
class="video closed"
data-metadata='{"end": 0.0, "speed": null, "ytTestTimeout": 1500, "publishCompletionUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@20f7e79d2987426da34b93e632b52610/handler/publish_completion", "ytApiUrl": "https://www.youtube.com/iframe_api", "showCaptions": "true", "streams": "1.00:iehI6-AhmKw", "poster": null, "saveStateEnabled": false, "start": 0.0, "completionPercentage": 0.95, "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@20f7e79d2987426da34b93e632b52610/handler/transcript/available_translations", "autoplay": false, "transcriptLanguages": {"en": "English"}, "autohideHtml5": false, "transcriptTranslationUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@20f7e79d2987426da34b93e632b52610/handler/transcript/translation/__lang__", "ytMetadataEndpoint": "", "generalSpeed": 1.0, "lmsRootURL": "https://openlearninglibrary.mit.edu", "autoAdvance": false, "completionEnabled": false, "savedVideoPosition": 0.0, "saveStateUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@20f7e79d2987426da34b93e632b52610/handler/xmodule_handler/save_user_state", "captionDataDir": null, "sources": [], "transcriptLanguage": "en", "recordedYoutubeIsAvailable": true, "prioritizeHls": false, "duration": 0.0}'
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="20f7e79d2987426da34b93e632b52610"></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_20f7e79d2987426da34b93e632b52610">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_20f7e79d2987426da34b93e632b52610">
<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@20f7e79d2987426da34b93e632b52610/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@20f7e79d2987426da34b93e632b52610/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-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@29704366e60142a797f370c0af4c70ac" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="vertical" data-request-token="49ee766cfe9111ee8e37026cc65ec0d9" data-has-score="False" data-runtime-version="1" data-init="VerticalStudentView">
<h2 class="hd hd-2 unit-title">The Busy Beaver Function</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@23e806ae8a454a979d5933b89a40c9c9">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@23e806ae8a454a979d5933b89a40c9c9" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="html" data-request-token="49ee766cfe9111ee8e37026cc65ec0d9" data-has-score="False" data-runtime-version="1" data-init="XBlockToXModuleShim">
<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;"> My favorite non-computable function is the Busy Beaver Function. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">It relies on the notion of <strong>Turing Machine productivity,</strong> which is defined as follows: if a Turing Machine yields output [mathjaxinline]k[/mathjaxinline] on an empty input, its productivity is [mathjaxinline]k[/mathjaxinline]; otherwise, its productivity is zero. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">The <strong>Busy Beaver Function,</strong> [mathjaxinline]BB(n)[/mathjaxinline], can then be defined as follows:</span></p>
<blockquote>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;"> [mathjaxinline]BB(n)[/mathjaxinline] = the productivity of the most productive (one-symbol) Turing Machine with [mathjaxinline]n[/mathjaxinline] states or fewer. </span></p>
</blockquote>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">Note that for each [mathjaxinline]n[/mathjaxinline] there are only finitely many one-symbol Turing Machines with [mathjaxinline]n[/mathjaxinline] states or fewer, so the Busy Beaver Function is guaranteed to be well-defined for each [mathjaxinline]n[/mathjaxinline]. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">One reason I like the Busy Beaver Function is that it is independent of one’s scheme for coding Turing Machines as natural numbers. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">Notice, in contrast, that the Halting Function only makes sense with respect to a particular coding scheme, since [mathjaxinline]H(k)[/mathjaxinline] is defined as being 1 if the [mathjaxinline]k[/mathjaxinline]th Turing Machine—according to one’s preferred coding scheme—halts on input [mathjaxinline]k[/mathjaxinline], and 0 otherwise.</span></p>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+24.118x+2T2020+type@video+block@b76978120b17494bb848d9150c65aea8">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-usage-id="block-v1:MITx+24.118x+2T2020+type@video+block@b76978120b17494bb848d9150c65aea8" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="video" data-request-token="49ee766cfe9111ee8e37026cc65ec0d9" data-has-score="False" data-runtime-version="1" data-init="XBlockToXModuleShim">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video Review: The Busy Beaver Function</h3>
<div
id="video_b76978120b17494bb848d9150c65aea8"
class="video closed"
data-metadata='{"end": 0.0, "speed": null, "ytTestTimeout": 1500, "publishCompletionUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@b76978120b17494bb848d9150c65aea8/handler/publish_completion", "ytApiUrl": "https://www.youtube.com/iframe_api", "showCaptions": "true", "streams": "1.00:GfQVc5wbzWI", "poster": null, "saveStateEnabled": false, "start": 0.0, "completionPercentage": 0.95, "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@b76978120b17494bb848d9150c65aea8/handler/transcript/available_translations", "autoplay": false, "transcriptLanguages": {"en": "English"}, "autohideHtml5": false, "transcriptTranslationUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@b76978120b17494bb848d9150c65aea8/handler/transcript/translation/__lang__", "ytMetadataEndpoint": "", "generalSpeed": 1.0, "lmsRootURL": "https://openlearninglibrary.mit.edu", "autoAdvance": false, "completionEnabled": false, "savedVideoPosition": 0.0, "saveStateUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@b76978120b17494bb848d9150c65aea8/handler/xmodule_handler/save_user_state", "captionDataDir": null, "sources": [], "transcriptLanguage": "en", "recordedYoutubeIsAvailable": true, "prioritizeHls": false, "duration": 0.0}'
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="b76978120b17494bb848d9150c65aea8"></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_b76978120b17494bb848d9150c65aea8">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_b76978120b17494bb848d9150c65aea8">
<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@b76978120b17494bb848d9150c65aea8/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@b76978120b17494bb848d9150c65aea8/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-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@fffc252b88574a83841d639eba0053be" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="vertical" data-request-token="49ee766cfe9111ee8e37026cc65ec0d9" data-has-score="False" data-runtime-version="1" data-init="VerticalStudentView">
<h2 class="hd hd-2 unit-title">A proof of non-computability</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@f24dcd2bb858438ab37ad4f980ab6320">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@f24dcd2bb858438ab37ad4f980ab6320" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="html" data-request-token="49ee766cfe9111ee8e37026cc65ec0d9" data-has-score="False" data-runtime-version="1" data-init="XBlockToXModuleShim">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p><span style="font-family: 'book antiqua', palatino;">Let us verify that the Busy Beaver Function is not Turing-Computable. (The result is due to Hungarian mathematician Tibor Radó.) As in the case of the Halting Function, we’ll proceed by <em>reductio</em>. More specifically, we’ll assume that there is a Turing Machine <span class="math inline">\(M^{BB}\)</span> that computes the Busy Beaver function, and show that that would allow us to construct an “impossible” Turing Machine <span class="math inline">\(M^I\)</span>. Here is how <span class="math inline">\(M^I\)</span> works, when given an empty input:</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;">For a particular number <span class="math inline">\(k\)</span> (to be specified below), <span class="math inline">\(M^I\)</span> starts by printing a sequence of <span class="math inline">\(k\)</span> ones on the tape, and then brings the reader to the beginning of the resulting sequence.</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;"><span class="math inline">\(M^I\)</span> duplicates the initial sequence of <span class="math inline">\(k\)</span> ones, and brings the reader to the beginning of the resulting sequence of <span class="math inline">\(2k\)</span> ones.</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;"><span class="math inline">\(M^I\)</span> applies <span class="math inline">\(M^{BB}\)</span>’s program as a subroutine, which results in a sequence of <span class="math inline">\(BB(2k)\)</span> ones.</span></p>
<p style="padding-left: 30px;"><span style="font-family: 'book antiqua', palatino;"><strong>Step 4</strong></span><br /><span style="font-family: 'book antiqua', palatino;"><span class="math inline">\(M^I\)</span> adds an additional one to the sequence of <span class="math inline">\(BB(2k)\)</span> ones, returns to the beginning of the sequence, and halts, yielding <span class="math inline">\(BB(2k)+1\)</span> as output.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">We will now prove that our impossible machine <span class="math inline">\(M^I\)</span> is indeed impossible. Here is the intuitive idea behind the proof. At Stage 3 of its operation, <span class="math inline">\(M^I\)</span> produces as long a sequence of ones as a machine with <span class="math inline">\(2k\)</span> could possibly produce. But we’ll see that <span class="math inline">\(M^I\)</span> is built using no more than <span class="math inline">\(2k\)</span> states. So at Stage 3 of its operation, <span class="math inline">\(M^I\)</span> produces as long a sequence of ones as it itself could possibly produce. So when, at Stage 4, <span class="math inline">\(M^I\)</span> adds a one to the sequence, it produces a <em>longer</em> string of ones than it itself could possibly produce, which is impossible.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">Formally speaking, we show that <span class="math inline">\(M^I\)</span> is impossible by verifying that its existence would allow us to prove each of the following inequalities (where <span class="math inline">\(\overline{M^I}\)</span> is the number of states in <span class="math inline">\(M^I\)</span>’s program):</span></p>
<dl><dt><strong><span style="font-family: 'book antiqua', palatino;">(E1)</span></strong></dt><dd>
<p><span class="math inline" style="font-family: 'book antiqua', palatino;">\(BB(\overline{M^I})\ge BB(2k)+1\)</span></p>
</dd><dt><strong><span style="font-family: 'book antiqua', palatino;">(E2)</span></strong></dt><dd>
<p><span class="math inline" style="font-family: 'book antiqua', palatino;">\(BB(\overline{M^I})<BB(2k)+1\)</span></p>
</dd></dl>
<h4><span style="font-family: 'book antiqua', palatino;">Proof of (E1)</span></h4>
<p><span style="font-family: 'book antiqua', palatino;">The construction of <span class="math inline">\(M^I\)</span> guarantees that <span class="math inline">\(M^I\)</span> delivers an output of <span class="math inline">\(BB(2k)+1\)</span>, given an empty input. So we know that the productivity of <span class="math inline">\(M^I\)</span> is <span class="math inline">\(BB(2k)+1\)</span>. But, by definition, <span class="math inline">\(BB(\overline{M^I})\)</span> is the productivity of the most productive Turing Machine with <span class="math inline">\(\overline{M^I}\)</span> states or less. Since <span class="math inline">\(M^I\)</span> has <span class="math inline">\(\overline{M^I}\)</span> states, and since its productivity is <span class="math inline">\(BB(2k)+1\)</span>, it must therefore be the case that <span class="math inline">\(BB(\overline{M^I})\ge BB(2k)+1\)</span>. In other words: (E1) must be true.</span></p>
<h4><span style="font-family: 'book antiqua', palatino;">Proof of (E2)</span></h4>
<p><span style="font-family: 'book antiqua', palatino;">We will now show that, when <span class="math inline">\(k\)</span> is chosen appropriately, (E2) must be true. We start with some notation:</span></p>
<ul>
<li>
<p><span style="font-family: 'book antiqua', palatino;">Let <span class="math inline">\(a_k\)</span> be the number of states <span class="math inline">\(M^I\)</span> used to implement Step 1 of its procedure.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">(As you’ll be asked to verify below, it is possible to build a Turing Machine that outputs <span class="math inline">\(k\)</span> on an empty input using <span class="math inline">\(k\)</span> states or less. So we may assume that <span class="math inline">\(a_k\le k\)</span>.)</span></p>
</li>
<li>
<p><span style="font-family: 'book antiqua', palatino;">Let <span class="math inline">\(b\)</span> be the minimum number of states <span class="math inline">\(M^I\)</span> uses to implement Step 2 of its procedure.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">(Since a fixed number of states can be used to duplicate sequences of ones of any length, <span class="math inline">\(b\)</span> can be assumed to be a constant, independent of <span class="math inline">\(k\)</span>.)</span></p>
</li>
<li>
<p><span style="font-family: 'book antiqua', palatino;">Let <span class="math inline">\(c\)</span> be the number of states <span class="math inline">\(M^I\)</span> uses to implement Step 3 of its procedure.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">(<span class="math inline">\(c\)</span> is simply the number of states in <span class="math inline">\(M^{BB}\)</span>, and is therefore a constant, independent of <span class="math inline">\(k\)</span>.)</span></p>
</li>
<li>
<p><span style="font-family: 'book antiqua', palatino;">Let <span class="math inline">\(d\)</span> be the number of states <span class="math inline">\(M^I\)</span> uses to implement Step 4 of its procedure.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">(Since a fixed number of states can be used to add an extra one at the end of a sequence of any length, <span class="math inline">\(d\)</span> can be assumed to be a constant independent of <span class="math inline">\(k\)</span>.)</span></p>
</li>
</ul>
<p><span style="font-family: 'book antiqua', palatino;">This allows us to count the number of states required by <span class="math inline">\(M^I\)</span>: <span class="math inline">\(a_k+b+c+d\)</span>. Since we know that <span class="math inline">\(a_k\le k\)</span>, the following must be true: <span class="math display">\[\overline{M^I}\le k+b+c+d\]</span> Let us now assume that <span class="math inline">\(k\)</span> is chosen so that it is at least as big as <span class="math inline">\(b+c+d\)</span>. We then have <span class="math inline">\(\overline{M^I}\le 2k\)</span>. From this it follows that <span class="math inline">\(BB(\overline{M^I})\le BB(2k)\)</span>, and therefore that <span class="math inline">\(BB(\overline{M^I}) < BB(2k)+1\)</span>. In other words: (E2) must be true.</span></p>
<h4><span style="font-family: 'book antiqua', palatino;">Summary</span></h4>
<p><span style="font-family: 'book antiqua', palatino;">By looking at <span class="math inline">\(M^I\)</span>’s output we showed that (E1) must be true. But by analyzing <span class="math inline">\(M^I\)</span>’s program we came to the contrary conclusion that (E2) must be true. So <span class="math inline">\(M^I\)</span> cannot exist. So <span class="math inline">\(M^{BB}\)</span> cannot exist. So the Busy Beaver Function isn’t Turing-computable.</span></p>
<p></p>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+24.118x+2T2020+type@video+block@4896284ef462422a9fd7280015a8e492">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-usage-id="block-v1:MITx+24.118x+2T2020+type@video+block@4896284ef462422a9fd7280015a8e492" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="video" data-request-token="49ee766cfe9111ee8e37026cc65ec0d9" data-has-score="False" data-runtime-version="1" data-init="XBlockToXModuleShim">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video Review: If the Busy Beaver Machine Exists, the Evil Machine Exists</h3>
<div
id="video_4896284ef462422a9fd7280015a8e492"
class="video closed"
data-metadata='{"end": 0.0, "speed": null, "ytTestTimeout": 1500, "publishCompletionUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@4896284ef462422a9fd7280015a8e492/handler/publish_completion", "ytApiUrl": "https://www.youtube.com/iframe_api", "showCaptions": "true", "streams": "1.00:tNl95QA0CIg", "poster": null, "saveStateEnabled": false, "start": 0.0, "completionPercentage": 0.95, "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@4896284ef462422a9fd7280015a8e492/handler/transcript/available_translations", "autoplay": false, "transcriptLanguages": {"en": "English"}, "autohideHtml5": false, "transcriptTranslationUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@4896284ef462422a9fd7280015a8e492/handler/transcript/translation/__lang__", "ytMetadataEndpoint": "", "generalSpeed": 1.0, "lmsRootURL": "https://openlearninglibrary.mit.edu", "autoAdvance": false, "completionEnabled": false, "savedVideoPosition": 0.0, "saveStateUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@4896284ef462422a9fd7280015a8e492/handler/xmodule_handler/save_user_state", "captionDataDir": null, "sources": [], "transcriptLanguage": "en", "recordedYoutubeIsAvailable": true, "prioritizeHls": false, "duration": 0.0}'
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="4896284ef462422a9fd7280015a8e492"></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_4896284ef462422a9fd7280015a8e492">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_4896284ef462422a9fd7280015a8e492">
<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@4896284ef462422a9fd7280015a8e492/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@4896284ef462422a9fd7280015a8e492/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@e6632f67457b4a71913feb3890cb8fe3">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-usage-id="block-v1:MITx+24.118x+2T2020+type@video+block@e6632f67457b4a71913feb3890cb8fe3" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="video" data-request-token="49ee766cfe9111ee8e37026cc65ec0d9" data-has-score="False" data-runtime-version="1" data-init="XBlockToXModuleShim">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video Review: The Evil Machine Does Not Exist</h3>
<div
id="video_e6632f67457b4a71913feb3890cb8fe3"
class="video closed"
data-metadata='{"end": 0.0, "speed": null, "ytTestTimeout": 1500, "publishCompletionUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@e6632f67457b4a71913feb3890cb8fe3/handler/publish_completion", "ytApiUrl": "https://www.youtube.com/iframe_api", "showCaptions": "true", "streams": "1.00:m5XzwUC1NMk", "poster": null, "saveStateEnabled": false, "start": 0.0, "completionPercentage": 0.95, "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@e6632f67457b4a71913feb3890cb8fe3/handler/transcript/available_translations", "autoplay": false, "transcriptLanguages": {"en": "English"}, "autohideHtml5": false, "transcriptTranslationUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@e6632f67457b4a71913feb3890cb8fe3/handler/transcript/translation/__lang__", "ytMetadataEndpoint": "", "generalSpeed": 1.0, "lmsRootURL": "https://openlearninglibrary.mit.edu", "autoAdvance": false, "completionEnabled": false, "savedVideoPosition": 0.0, "saveStateUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@e6632f67457b4a71913feb3890cb8fe3/handler/xmodule_handler/save_user_state", "captionDataDir": null, "sources": [], "transcriptLanguage": "en", "recordedYoutubeIsAvailable": true, "prioritizeHls": false, "duration": 0.0}'
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="e6632f67457b4a71913feb3890cb8fe3"></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_e6632f67457b4a71913feb3890cb8fe3">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_e6632f67457b4a71913feb3890cb8fe3">
<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@e6632f67457b4a71913feb3890cb8fe3/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@e6632f67457b4a71913feb3890cb8fe3/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@video+block@f2b422f7393b45eeaae5ff31f3a58576">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-usage-id="block-v1:MITx+24.118x+2T2020+type@video+block@f2b422f7393b45eeaae5ff31f3a58576" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="video" data-request-token="49ee766cfe9111ee8e37026cc65ec0d9" data-has-score="False" data-runtime-version="1" data-init="XBlockToXModuleShim">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video Review: The Evil Machine, Step by Step</h3>
<div
id="video_f2b422f7393b45eeaae5ff31f3a58576"
class="video closed"
data-metadata='{"end": 0.0, "speed": null, "ytTestTimeout": 1500, "publishCompletionUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@f2b422f7393b45eeaae5ff31f3a58576/handler/publish_completion", "ytApiUrl": "https://www.youtube.com/iframe_api", "showCaptions": "true", "streams": "1.00:aAScfcR91ds", "poster": null, "saveStateEnabled": false, "start": 0.0, "completionPercentage": 0.95, "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@f2b422f7393b45eeaae5ff31f3a58576/handler/transcript/available_translations", "autoplay": false, "transcriptLanguages": {"en": "English"}, "autohideHtml5": false, "transcriptTranslationUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@f2b422f7393b45eeaae5ff31f3a58576/handler/transcript/translation/__lang__", "ytMetadataEndpoint": "", "generalSpeed": 1.0, "lmsRootURL": "https://openlearninglibrary.mit.edu", "autoAdvance": false, "completionEnabled": false, "savedVideoPosition": 0.0, "saveStateUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@f2b422f7393b45eeaae5ff31f3a58576/handler/xmodule_handler/save_user_state", "captionDataDir": null, "sources": [], "transcriptLanguage": "en", "recordedYoutubeIsAvailable": true, "prioritizeHls": false, "duration": 0.0}'
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="f2b422f7393b45eeaae5ff31f3a58576"></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_f2b422f7393b45eeaae5ff31f3a58576">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_f2b422f7393b45eeaae5ff31f3a58576">
<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@f2b422f7393b45eeaae5ff31f3a58576/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@f2b422f7393b45eeaae5ff31f3a58576/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
<div class="vert vert-4" data-id="block-v1:MITx+24.118x+2T2020+type@problem+block@35116224c5c04dc9ac988462ece12bfe">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@35116224c5c04dc9ac988462ece12bfe" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="problem" data-request-token="49ee766cfe9111ee8e37026cc65ec0d9" data-has-score="True" data-runtime-version="1" data-init="XBlockToXModuleShim">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_35116224c5c04dc9ac988462ece12bfe" class="problems-wrapper" role="group"
aria-labelledby="35116224c5c04dc9ac988462ece12bfe-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@35116224c5c04dc9ac988462ece12bfe" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@35116224c5c04dc9ac988462ece12bfe/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="35116224c5c04dc9ac988462ece12bfe-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@35116224c5c04dc9ac988462ece12bfe-problem-progress" tabindex="-1">
Problem 1
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@35116224c5c04dc9ac988462ece12bfe-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;">True or false?</span>
</p>
<blockquote>
<p>
<span style="font-family: 'book antiqua', palatino;">For any natural number <span class="math inline">\(k\)</span>, it is possible to build a Turing Machine that outputs <span class="math inline">\(k\)</span> on an empty input, using <span class="math inline">\(k\)</span> states or less.</span>
</p>
</blockquote>
<div class="choicegroup capa_inputtype" id="inputtype_35116224c5c04dc9ac988462ece12bfe_2_1">
<fieldset aria-describedby="status_35116224c5c04dc9ac988462ece12bfe_2_1">
<div class="field">
<input type="radio" name="input_35116224c5c04dc9ac988462ece12bfe_2_1" id="input_35116224c5c04dc9ac988462ece12bfe_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="35116224c5c04dc9ac988462ece12bfe_2_1-choice_0-label" for="input_35116224c5c04dc9ac988462ece12bfe_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_35116224c5c04dc9ac988462ece12bfe_2_1">
<span style="font-family: 'book antiqua', palatino;">True</span>
</label>
</div>
<div class="field">
<input type="radio" name="input_35116224c5c04dc9ac988462ece12bfe_2_1" id="input_35116224c5c04dc9ac988462ece12bfe_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="35116224c5c04dc9ac988462ece12bfe_2_1-choice_1-label" for="input_35116224c5c04dc9ac988462ece12bfe_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_35116224c5c04dc9ac988462ece12bfe_2_1">
<span style="font-family: 'book antiqua', palatino;">False</span>
</label>
</div>
<span id="answer_35116224c5c04dc9ac988462ece12bfe_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_35116224c5c04dc9ac988462ece12bfe_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_35116224c5c04dc9ac988462ece12bfe_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_35116224c5c04dc9ac988462ece12bfe" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_35116224c5c04dc9ac988462ece12bfe">
<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="35116224c5c04dc9ac988462ece12bfe-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="35116224c5c04dc9ac988462ece12bfe-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="35116224c5c04dc9ac988462ece12bfe-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@3dfb03229a3c42a9928126b5b113b199">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@3dfb03229a3c42a9928126b5b113b199" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="problem" data-request-token="49ee766cfe9111ee8e37026cc65ec0d9" data-has-score="True" data-runtime-version="1" data-init="XBlockToXModuleShim">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_3dfb03229a3c42a9928126b5b113b199" class="problems-wrapper" role="group"
aria-labelledby="3dfb03229a3c42a9928126b5b113b199-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@3dfb03229a3c42a9928126b5b113b199" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@3dfb03229a3c42a9928126b5b113b199/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="3dfb03229a3c42a9928126b5b113b199-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@3dfb03229a3c42a9928126b5b113b199-problem-progress" tabindex="-1">
Problem 2
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@3dfb03229a3c42a9928126b5b113b199-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;">True or false?</span>
</p>
<blockquote>
<p>
<span style="font-family: 'book antiqua', palatino;">For some fixed constant <span class="math inline">\(c\)</span>, it is possible to build a one-symbol Turing Machine that uses at most <span class="math inline">\(|\log_2k| + c\)</span> states and outputs <span class="math inline">\(k^2\)</span>, on an empty input.</span>
</p>
</blockquote>
<div class="choicegroup capa_inputtype" id="inputtype_3dfb03229a3c42a9928126b5b113b199_2_1">
<fieldset aria-describedby="status_3dfb03229a3c42a9928126b5b113b199_2_1">
<div class="field">
<input type="radio" name="input_3dfb03229a3c42a9928126b5b113b199_2_1" id="input_3dfb03229a3c42a9928126b5b113b199_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="3dfb03229a3c42a9928126b5b113b199_2_1-choice_0-label" for="input_3dfb03229a3c42a9928126b5b113b199_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_3dfb03229a3c42a9928126b5b113b199_2_1">
<span style="font-family: 'book antiqua', palatino;">True</span>
</label>
</div>
<div class="field">
<input type="radio" name="input_3dfb03229a3c42a9928126b5b113b199_2_1" id="input_3dfb03229a3c42a9928126b5b113b199_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="3dfb03229a3c42a9928126b5b113b199_2_1-choice_1-label" for="input_3dfb03229a3c42a9928126b5b113b199_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_3dfb03229a3c42a9928126b5b113b199_2_1">
<span style="font-family: 'book antiqua', palatino;">False</span>
</label>
</div>
<span id="answer_3dfb03229a3c42a9928126b5b113b199_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_3dfb03229a3c42a9928126b5b113b199_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_3dfb03229a3c42a9928126b5b113b199_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_3dfb03229a3c42a9928126b5b113b199" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_3dfb03229a3c42a9928126b5b113b199">
<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="3dfb03229a3c42a9928126b5b113b199-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="3dfb03229a3c42a9928126b5b113b199-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="3dfb03229a3c42a9928126b5b113b199-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@977aba499aa04c57acae607a4792b9f1">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@977aba499aa04c57acae607a4792b9f1" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="problem" data-request-token="49ee766cfe9111ee8e37026cc65ec0d9" data-has-score="True" data-runtime-version="1" data-init="XBlockToXModuleShim">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_977aba499aa04c57acae607a4792b9f1" class="problems-wrapper" role="group"
aria-labelledby="977aba499aa04c57acae607a4792b9f1-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@977aba499aa04c57acae607a4792b9f1" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@977aba499aa04c57acae607a4792b9f1/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="2"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="977aba499aa04c57acae607a4792b9f1-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@977aba499aa04c57acae607a4792b9f1-problem-progress" tabindex="-1">
Problem 3
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@977aba499aa04c57acae607a4792b9f1-problem-progress"></div>
<div class="problem">
<div>
<p>
<span style="font-family: 'book antiqua', palatino;">Determine the productivity of each of the following Turing Machines:</span>
</p>
<p>
<span style="font-family: 'book antiqua', palatino;">
<span class="math display">\[\begin{array}{ccccc}
0 &amp;\_ &amp;1 &amp;r &amp;0 \\
\end{array}\]</span>
</span>
</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="formulaequationinput_977aba499aa04c57acae607a4792b9f1_2_1" class="inputtype formulaequationinput">
<div class="unanswered">
<input type="text" name="input_977aba499aa04c57acae607a4792b9f1_2_1" id="input_977aba499aa04c57acae607a4792b9f1_2_1" data-input-id="977aba499aa04c57acae607a4792b9f1_2_1" value="" aria-describedby="status_977aba499aa04c57acae607a4792b9f1_2_1" size="20"/>
<span class="trailing_text" id="trailing_text_977aba499aa04c57acae607a4792b9f1_2_1"/>
<span class="status unanswered" id="status_977aba499aa04c57acae607a4792b9f1_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_977aba499aa04c57acae607a4792b9f1_2_1" class="answer"/>
<div id="input_977aba499aa04c57acae607a4792b9f1_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>
<p>
<span style="font-family: 'book antiqua', palatino;">
<span class="math display">\[\begin{array}{ccccc}
0 &amp;\_ &amp;1 &amp;* &amp;1 \\
\end{array}\]</span>
</span>
</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div id="formulaequationinput_977aba499aa04c57acae607a4792b9f1_3_1" class="inputtype formulaequationinput">
<div class="unanswered">
<input type="text" name="input_977aba499aa04c57acae607a4792b9f1_3_1" id="input_977aba499aa04c57acae607a4792b9f1_3_1" data-input-id="977aba499aa04c57acae607a4792b9f1_3_1" value="" aria-describedby="status_977aba499aa04c57acae607a4792b9f1_3_1" size="20"/>
<span class="trailing_text" id="trailing_text_977aba499aa04c57acae607a4792b9f1_3_1"/>
<span class="status unanswered" id="status_977aba499aa04c57acae607a4792b9f1_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_977aba499aa04c57acae607a4792b9f1_3_1" class="answer"/>
<div id="input_977aba499aa04c57acae607a4792b9f1_3_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>
</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_977aba499aa04c57acae607a4792b9f1" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_977aba499aa04c57acae607a4792b9f1">
<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="977aba499aa04c57acae607a4792b9f1-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="977aba499aa04c57acae607a4792b9f1-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="977aba499aa04c57acae607a4792b9f1-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@6c0a7b06ce354068bb909c0e98b4887f">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@6c0a7b06ce354068bb909c0e98b4887f" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="problem" data-request-token="49ee766cfe9111ee8e37026cc65ec0d9" data-has-score="True" data-runtime-version="1" data-init="XBlockToXModuleShim">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_6c0a7b06ce354068bb909c0e98b4887f" class="problems-wrapper" role="group"
aria-labelledby="6c0a7b06ce354068bb909c0e98b4887f-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@6c0a7b06ce354068bb909c0e98b4887f" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@6c0a7b06ce354068bb909c0e98b4887f/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="6c0a7b06ce354068bb909c0e98b4887f-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@6c0a7b06ce354068bb909c0e98b4887f-problem-progress" tabindex="-1">
Problem 4
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@6c0a7b06ce354068bb909c0e98b4887f-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;">True or false?</span>
</p>
<blockquote>
<p>
<span style="font-family: 'book antiqua', palatino;"><span class="math inline">\(BB(n)\)</span> grows faster than any Turing-computable function. (More specifically: for any Turing-computable function <span class="math inline">\(f(n)\)</span>, there is an <span class="math inline">\(m\)</span> such that, for every <span class="math inline">\(n&gt;m\)</span>, <span class="math inline">\(BB(n)&gt;f(n)\)</span>.)</span>
</p>
</blockquote>
<div class="choicegroup capa_inputtype" id="inputtype_6c0a7b06ce354068bb909c0e98b4887f_2_1">
<fieldset aria-describedby="status_6c0a7b06ce354068bb909c0e98b4887f_2_1">
<div class="field">
<input type="radio" name="input_6c0a7b06ce354068bb909c0e98b4887f_2_1" id="input_6c0a7b06ce354068bb909c0e98b4887f_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="6c0a7b06ce354068bb909c0e98b4887f_2_1-choice_0-label" for="input_6c0a7b06ce354068bb909c0e98b4887f_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_6c0a7b06ce354068bb909c0e98b4887f_2_1">
<span style="font-family: 'book antiqua', palatino;">True</span>
</label>
</div>
<div class="field">
<input type="radio" name="input_6c0a7b06ce354068bb909c0e98b4887f_2_1" id="input_6c0a7b06ce354068bb909c0e98b4887f_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="6c0a7b06ce354068bb909c0e98b4887f_2_1-choice_1-label" for="input_6c0a7b06ce354068bb909c0e98b4887f_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_6c0a7b06ce354068bb909c0e98b4887f_2_1">
<span style="font-family: 'book antiqua', palatino;">False</span>
</label>
</div>
<span id="answer_6c0a7b06ce354068bb909c0e98b4887f_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_6c0a7b06ce354068bb909c0e98b4887f_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_6c0a7b06ce354068bb909c0e98b4887f_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_6c0a7b06ce354068bb909c0e98b4887f" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_6c0a7b06ce354068bb909c0e98b4887f">
<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="6c0a7b06ce354068bb909c0e98b4887f-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="6c0a7b06ce354068bb909c0e98b4887f-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="6c0a7b06ce354068bb909c0e98b4887f-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