<div class="xblock xblock-public_view xblock-public_view-vertical" data-runtime-class="LmsRuntime" data-has-score="False" data-init="VerticalStudentView" data-block-type="vertical" data-runtime-version="1" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@bbbe2e2d25644079a59e3c6979e7a4fb" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="15b898665ace11ef94ec022c6f26e6af" data-graded="False">
<h2 class="hd hd-2 unit-title">The Big Number Duel (Optional)</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@5e1ebfbeeffd453fbbd11f0bf9b4477a">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-runtime-class="LmsRuntime" data-has-score="False" data-init="XBlockToXModuleShim" data-block-type="html" data-runtime-version="1" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@5e1ebfbeeffd453fbbd11f0bf9b4477a" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="15b898665ace11ef94ec022c6f26e6af" data-graded="False">
<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;"> Imagine the following competition: two contestants, one blackboard, biggest number wins. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">My friend <a href="http://www.princeton.edu/~adame/" target="_blank">Adam Elga</a>, a philosopher at Princeton University, challenged me to such a duel after reading <a href="http://www.scottaaronson.com/" target="_blank">Scott Aaronson</a>’s <a href="http://www.scottaaronson.com/writings/bignumbers.html" target="_blank">“Who Can Name the Bigger Number?”</a>. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">This (optional) final lecture is a blow-by-blow account of our mighty confrontation.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">(You can check out the poster that Adam designed for the event <a href="http://mit.edu/philos/www/poster.pdf" target="[object Object]" style="line-height: 1.6;">here</a>, <em style="line-height: 1.6;">The Tech</em>'s reporting <a href="http://www-tech.mit.edu/V126/N64/64largenumber.html" target="[object Object]" style="line-height: 1.6;">here</a>, and a Numberphile video about the contest <a href="https://www.youtube.com/watch?v=X3l0fPHZja8" target="[object Object]">here</a>.)</span></p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-runtime-class="LmsRuntime" data-has-score="False" data-init="VerticalStudentView" data-block-type="vertical" data-runtime-version="1" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@e4cde9fbf5d74c5484c5736495c1bafd" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="15b898665ace11ef94ec022c6f26e6af" data-graded="False">
<h2 class="hd hd-2 unit-title">The rules of the game</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@82b2dfd4453d4079ac5263dd96ab126e">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-runtime-class="LmsRuntime" data-has-score="False" data-init="XBlockToXModuleShim" data-block-type="html" data-runtime-version="1" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@82b2dfd4453d4079ac5263dd96ab126e" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="15b898665ace11ef94ec022c6f26e6af" data-graded="False">
<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 began by fixing some rules. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">The first rule is that we would take turns writing numbers on the board, and that the last person to write down a valid entry would be the winner. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">The second rule is that only finite numbers would be allowed. The number 17, for example, would count as a valid entry as would the number 1,010,101,010, but not [mathjaxinline]\omega[/mathjaxinline] or [mathjaxinline]\omega +\omega[/mathjaxinline]. </span></p>
<p><span style="font-family: 'book antiqua', palatino;"><span style="font-size: 12pt;">The third rule is that semantic vocabulary—expressions like “names” or “refers to” or “is true of”—would be disallowed. This restriction is crucial. Without it, Adam would have been in a position to write “the biggest number ever named by Agustín, plus one” on the board, and win on the first round. (Worse still: I would have been able to also write “the biggest number ever named by Adam, plus one”, leaving us with a problem.)</span></span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">Finally, we agreed not to engage in unsporting behavior. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">Each time one of us wrote a number on the board, the other would either recognize defeat or respond with a much bigger number. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">How much bigger? </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">Big enough that it would be impossible to reach it in practice (e.g. before someone got hungry and left) using only methods that had been introduced in previous stages of the competition. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">That means, for example, that if, a little ways into the competition, Adam”s last entry was “101010”, it would be unsporting for me to respond with “101010+ 1”, or with “10101010”. For either of these numbers can be reached, in a relatively short time, using methods that had already been introduced. We wanted the competition to be a war of originality, not a war of patience!</span></p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-runtime-class="LmsRuntime" data-has-score="False" data-init="VerticalStudentView" data-block-type="vertical" data-runtime-version="1" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@0b514b5db08a4458bb7954bc5cd28aa4" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="15b898665ace11ef94ec022c6f26e6af" data-graded="False">
<h2 class="hd hd-2 unit-title">The First Three Rounds</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@4d325cc9d7cc47b9a7b5b0ea789b5465">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-runtime-class="LmsRuntime" data-has-score="False" data-init="XBlockToXModuleShim" data-block-type="html" data-runtime-version="1" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@4d325cc9d7cc47b9a7b5b0ea789b5465" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="15b898665ace11ef94ec022c6f26e6af" data-graded="False">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;"> The competition took place at MIT. As the hometown hero, I got to go first. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">Without thinking too much about it I wrote down a sequence of thirty or forty ones </span></p>
<center>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">[mathjaxinline]111111111111111111111111111111 [/mathjaxinline] </span></p>
</center>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">“We’re still warming up”, I thought. But my first effort proved disastrous. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">Adam approached the board with an eraser, and erased a line across all but the first two of my ones, leaving</span></p>
<center><span style="font-family: 'book antiqua', palatino;">[mathjaxinline]11\,!\,!\,!\,!\,!\,!\,!\,!\,!\,!\,!\,!\,!\,!\,!\,!\,!\,!\,!\,!\,!\,!\,!\,!\,!\,!\,!\,![/mathjaxinline]</span></center>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">“Eleven factorial, factorial, factorial, [mathjaxinline] \dots[/mathjaxinline]”, he declared triumphantly. [mathjaxinline]11![/mathjaxinline] is 39,916,800, [mathjaxinline]11!![/mathjaxinline] is approximately [mathjaxinline]610^{286,078,170}[/mathjaxinline] (which is much more than the number of particles in the universe); [mathjaxinline]11!!![/mathjaxinline] is so big that it cannot be written using an expression of the form "[mathjaxinline]10^n[/mathjaxinline]" in a practical amount of time, where "[mathjaxinline]n[/mathjaxinline]" is a numeral in base 10. So [mathjaxinline]11!!![/mathjaxinline] definitely cannot be reached, in practice, by writing a long sequence of ones on the blackboard! </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">Adam’s entry was much bigger than mine. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">Fortunately, I was able to remember the Busy Beaver function, [mathjaxinline]BB(n)[/mathjaxinline]. So my next entry was [mathjaxinline]BB(10^{100}[/mathjaxinline]): the productivity of the most productive Turing Machine with a googol states or less. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">How does this number compare to Adam’s last entry? It is possible to write a relatively short Turing Machine program that computes the factorial function, and outputs the result of applying the function 30 or 40 times, starting with 11—or, indeed, the result of applying the function [mathjaxinline]10^{10^{10^{10}}}[/mathjaxinline] times starting with 11. I don’t know how many states it takes to do so, but the number is certainly smaller than [mathjaxinline]10^{100}[/mathjaxinline]. It follows that [mathjaxinline]BB(10^{100})[/mathjaxinline] is bigger than Adam’s last entry. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">In fact, it is much, much larger.</span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;"> [mathjaxinline]BB(10^{100})[/mathjaxinline] is a truly gigantic number: no matter how big a number [mathjaxinline]g[/mathjaxinline] is, as long as it is possible, in practice, to program a computer to output it, [mathjaxinline]g[/mathjaxinline] will be smaller than [mathjaxinline]BB(10^{100})[/mathjaxinline], since every program we can write in practice will have fewer than [mathjaxinline]10^{100}[/mathjaxinline] states.</span></p>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+24.118x+2T2020+type@video+block@3be22b52501943e4a24c0fc27e4400bc">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-runtime-class="LmsRuntime" data-has-score="False" data-init="XBlockToXModuleShim" data-block-type="video" data-runtime-version="1" data-usage-id="block-v1:MITx+24.118x+2T2020+type@video+block@3be22b52501943e4a24c0fc27e4400bc" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="15b898665ace11ef94ec022c6f26e6af" data-graded="False">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video Review: The Rules, and The First Few Rounds</h3>
<div
id="video_3be22b52501943e4a24c0fc27e4400bc"
class="video closed"
data-metadata='{"captionDataDir": null, "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@3be22b52501943e4a24c0fc27e4400bc/handler/transcript/available_translations", "start": 0.0, "savedVideoPosition": 0.0, "generalSpeed": 1.0, "saveStateEnabled": false, "transcriptLanguage": "en", "publishCompletionUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@3be22b52501943e4a24c0fc27e4400bc/handler/publish_completion", "lmsRootURL": "https://openlearninglibrary.mit.edu", "ytApiUrl": "https://www.youtube.com/iframe_api", "autoAdvance": false, "saveStateUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@3be22b52501943e4a24c0fc27e4400bc/handler/xmodule_handler/save_user_state", "completionEnabled": false, "prioritizeHls": false, "sources": [], "completionPercentage": 0.95, "transcriptTranslationUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@3be22b52501943e4a24c0fc27e4400bc/handler/transcript/translation/__lang__", "transcriptLanguages": {"en": "English"}, "streams": "1.00:l9MjtP5bEzQ", "showCaptions": "true", "speed": null, "ytMetadataEndpoint": "", "autohideHtml5": false, "duration": 0.0, "poster": null, "recordedYoutubeIsAvailable": true, "end": 0.0, "ytTestTimeout": 1500, "autoplay": false}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="3be22b52501943e4a24c0fc27e4400bc"></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_3be22b52501943e4a24c0fc27e4400bc">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_3be22b52501943e4a24c0fc27e4400bc">
<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@3be22b52501943e4a24c0fc27e4400bc/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@3be22b52501943e4a24c0fc27e4400bc/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-runtime-class="LmsRuntime" data-has-score="False" data-init="VerticalStudentView" data-block-type="vertical" data-runtime-version="1" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@9ad033ef5d534040b804c48e204919fd" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="15b898665ace11ef94ec022c6f26e6af" data-graded="False">
<h2 class="hd hd-2 unit-title">Beyond Busy Beaver</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@d8b1d107753940e68729c110f3b61171">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-runtime-class="LmsRuntime" data-has-score="False" data-init="XBlockToXModuleShim" data-block-type="html" data-runtime-version="1" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@d8b1d107753940e68729c110f3b61171" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="15b898665ace11ef94ec022c6f26e6af" data-graded="False">
<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;"> Over the next few rounds, the duel became a search for more and more powerful generalizations of the notion of a Turing Machine. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">Imagine equipping a Turing Machine with a “halting oracle”: a primitive operation that allows it to instantaneously determine whether an ordinary Turing Machine would halt on an empty input. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">Call this new kind of machine a Super Turing-Machine. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">We know that the Busy Beaver function is not Turing-computable. But, as you’ll be asked to verify in an exercise below, it can be computed using a Super Turing-Machine. As you’ll also be asked to verify below, this means that for any ordinary Turing Machine with sufficiently many states, there is a super Turing Machine that has fewer states but is much more productive. This means that the function [mathjaxinline]BB_1(n)[/mathjaxinline]—i.e. the Busy Beaver function for super Turing Machines—can be used to express numbers which are much bigger than [mathjaxinline]BB(10^{100})[/mathjaxinline](for instance:[mathjaxinline]BB_1(10^{100})[/mathjaxinline]).</span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;"> As one might have expected, no super Turing Machine can compute [mathjaxinline]BB_1(n)[/mathjaxinline]. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">But we could compute this function using a super-duper Turing Machine: a Turing Machine with a halting oracle for super Turing Machines. And [mathjaxinline]BB_2(10^{100})[/mathjaxinline]—the Busy Beaver function for super-duper Turing Machines—can be used to express numbers which are much bigger than [mathjaxinline]BB_1(10^{100})[/mathjaxinline].</span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">It goes without saying that by considering more and more powerful oracles, one can extend the hierarchy of Busy Beaver functions further still. After \(BB(n)\) and \(BB_1(n)\) come \(BB_2(n)\),\(BB_3(n)\), and so forth. Then come \(BB_\omega(n)\), \(BB_{\omega+1}(n)\), \(BB_{\omega+2}(n),\dots, BB_{\omega+\omega}(n),\dots, BB_{\omega+\omega+\omega}(n),\ldots, BB_{\omega\times\omega}(n),\dots BB_{\omega\times\omega\times\omega}(n)\ldots\)</span><span style="font-size: 12pt; font-family: 'book antiqua', palatino;"><span style="font-size: 12pt; font-family: 'book antiqua', palatino;"></span>. And do forth. (It is worth noting that even if \(\alpha\) is an infinite ordinal, \(BB_\alpha (10^{100})\) is a finite number and therefore a valid entry to the competition.)<br /><br />The most powerful Busy Beaver function that Adam and I considered was \(BB_\theta (n)\), where \(\theta\) is the first non-recursive ordinal---a relatively small infinite ordinal. So the next entry to the competition was \(BB_\theta (10^{100})\). And although it's not generally true that \(BB_\alpha (10^{100})\) is strictly larger than \( BB_\beta (10^{100})\) when \(\alpha > \beta\), it's certainly true that \(BB_\theta (10^{100})\) is much, much bigger than \(BB_1(10^{100})\), which had been our previous entry. <br /><br /></span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">The last entry to the competition, the winning entry, was a bigger number still: </span></p>
<blockquote>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">The smallest number with the property of being larger than any number that can be named in the language of set theory using [mathjaxinline]10^{100}[/mathjaxinline] symbols or less. </span></p>
</blockquote>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">This particular way of describing the number wouldn't have been a valid entry to the competition because it includes the expression "named'', which counts as semantic vocabulary and is therefore ruled out. But the description that was actually used in the competition didn't rely on forbidden vocabulary. It instead relied on a second order language: a language that is capable of expressing not just singular quantification ("there is a number such that it is so and so") but also plural quantification ("there are some numbers such that they are so and so"). Second-order languages are so powerful that they allow us to characterize a non-semantic substitute for the notion of being named in the language of set theory using \(10^{100}\) symbols or less.<br /><br />And what if we had a language that was even more expressive than a second-order language? A third-order language -- a language capable of expressing "super plural'' quantification -- would be so powerful that it would allow us to characterize a non-semantic substitute for the notion of being named in the language of <em>second-order</em> set theory using \(10^{100}\) symbols or less. And that would allow one to name a number even bigger than the winning entry of our competition. Our quest to find larger and larger numbers has now morphed into a quest to find more and more powerful languages!<br /><br /></span></p>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+24.118x+2T2020+type@video+block@4770d6427d3b44fa826a72c11baf2c1f">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-runtime-class="LmsRuntime" data-has-score="False" data-init="XBlockToXModuleShim" data-block-type="video" data-runtime-version="1" data-usage-id="block-v1:MITx+24.118x+2T2020+type@video+block@4770d6427d3b44fa826a72c11baf2c1f" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="15b898665ace11ef94ec022c6f26e6af" data-graded="False">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video Review: Beyond the Busy Beaver</h3>
<div
id="video_4770d6427d3b44fa826a72c11baf2c1f"
class="video closed"
data-metadata='{"captionDataDir": null, "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@4770d6427d3b44fa826a72c11baf2c1f/handler/transcript/available_translations", "start": 0.0, "savedVideoPosition": 0.0, "generalSpeed": 1.0, "saveStateEnabled": false, "transcriptLanguage": "en", "publishCompletionUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@4770d6427d3b44fa826a72c11baf2c1f/handler/publish_completion", "lmsRootURL": "https://openlearninglibrary.mit.edu", "ytApiUrl": "https://www.youtube.com/iframe_api", "autoAdvance": false, "saveStateUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@4770d6427d3b44fa826a72c11baf2c1f/handler/xmodule_handler/save_user_state", "completionEnabled": false, "prioritizeHls": false, "sources": [], "completionPercentage": 0.95, "transcriptTranslationUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@4770d6427d3b44fa826a72c11baf2c1f/handler/transcript/translation/__lang__", "transcriptLanguages": {"en": "English"}, "streams": "1.00:ruPjy0S-dMg", "showCaptions": "true", "speed": null, "ytMetadataEndpoint": "", "autohideHtml5": false, "duration": 0.0, "poster": null, "recordedYoutubeIsAvailable": true, "end": 0.0, "ytTestTimeout": 1500, "autoplay": false}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="4770d6427d3b44fa826a72c11baf2c1f"></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>
</div>
</div>
</div>
<div class="vert vert-2" data-id="block-v1:MITx+24.118x+2T2020+type@problem+block@e4cab341447c4081826e22b2ddc78d1b">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-runtime-class="LmsRuntime" data-has-score="True" data-init="XBlockToXModuleShim" data-block-type="problem" data-runtime-version="1" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@e4cab341447c4081826e22b2ddc78d1b" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="15b898665ace11ef94ec022c6f26e6af" data-graded="False">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_e4cab341447c4081826e22b2ddc78d1b" class="problems-wrapper" role="group"
aria-labelledby="e4cab341447c4081826e22b2ddc78d1b-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@e4cab341447c4081826e22b2ddc78d1b" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@e4cab341447c4081826e22b2ddc78d1b/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="e4cab341447c4081826e22b2ddc78d1b-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@e4cab341447c4081826e22b2ddc78d1b-problem-progress" tabindex="-1">
Problem 1
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@e4cab341447c4081826e22b2ddc78d1b-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;">Give an informal description of how a super-Turing Machine might compute <span class="math inline">\(BB(n)\)</span>.</span>
</p>
<div class="choicegroup capa_inputtype" id="inputtype_e4cab341447c4081826e22b2ddc78d1b_2_1">
<fieldset aria-describedby="status_e4cab341447c4081826e22b2ddc78d1b_2_1">
<div class="field">
<input type="checkbox" name="input_e4cab341447c4081826e22b2ddc78d1b_2_1[]" id="input_e4cab341447c4081826e22b2ddc78d1b_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="e4cab341447c4081826e22b2ddc78d1b_2_1-choice_0-label" for="input_e4cab341447c4081826e22b2ddc78d1b_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_e4cab341447c4081826e22b2ddc78d1b_2_1">
<span style="font-family: 'book antiqua', palatino;">Done</span>
</label>
</div>
<span id="answer_e4cab341447c4081826e22b2ddc78d1b_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_e4cab341447c4081826e22b2ddc78d1b_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_e4cab341447c4081826e22b2ddc78d1b_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_e4cab341447c4081826e22b2ddc78d1b" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_e4cab341447c4081826e22b2ddc78d1b">
<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="e4cab341447c4081826e22b2ddc78d1b-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="e4cab341447c4081826e22b2ddc78d1b-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="e4cab341447c4081826e22b2ddc78d1b-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@5e219f0a204247edbf1bf52ed36e157a">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-runtime-class="LmsRuntime" data-has-score="True" data-init="XBlockToXModuleShim" data-block-type="problem" data-runtime-version="1" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@5e219f0a204247edbf1bf52ed36e157a" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="15b898665ace11ef94ec022c6f26e6af" data-graded="False">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_5e219f0a204247edbf1bf52ed36e157a" class="problems-wrapper" role="group"
aria-labelledby="5e219f0a204247edbf1bf52ed36e157a-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@5e219f0a204247edbf1bf52ed36e157a" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@5e219f0a204247edbf1bf52ed36e157a/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="5e219f0a204247edbf1bf52ed36e157a-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@5e219f0a204247edbf1bf52ed36e157a-problem-progress" tabindex="-1">
Problem 2
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@5e219f0a204247edbf1bf52ed36e157a-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;">There is a number <span class="math inline">\(k\)</span> such that for any ordinary Turing Machine with more than <span class="math inline">\(k\)</span> states, there is a super Turing Machine that has fewer states but is much more productive.</span>
</p>
</blockquote>
<div class="choicegroup capa_inputtype" id="inputtype_5e219f0a204247edbf1bf52ed36e157a_2_1">
<fieldset aria-describedby="status_5e219f0a204247edbf1bf52ed36e157a_2_1">
<div class="field">
<input type="radio" name="input_5e219f0a204247edbf1bf52ed36e157a_2_1" id="input_5e219f0a204247edbf1bf52ed36e157a_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="5e219f0a204247edbf1bf52ed36e157a_2_1-choice_0-label" for="input_5e219f0a204247edbf1bf52ed36e157a_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_5e219f0a204247edbf1bf52ed36e157a_2_1">
<span style="font-family: 'book antiqua', palatino;">True</span>
</label>
</div>
<div class="field">
<input type="radio" name="input_5e219f0a204247edbf1bf52ed36e157a_2_1" id="input_5e219f0a204247edbf1bf52ed36e157a_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="5e219f0a204247edbf1bf52ed36e157a_2_1-choice_1-label" for="input_5e219f0a204247edbf1bf52ed36e157a_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_5e219f0a204247edbf1bf52ed36e157a_2_1">
<span style="font-family: 'book antiqua', palatino;">False</span>
</label>
</div>
<span id="answer_5e219f0a204247edbf1bf52ed36e157a_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_5e219f0a204247edbf1bf52ed36e157a_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_5e219f0a204247edbf1bf52ed36e157a_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_5e219f0a204247edbf1bf52ed36e157a" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_5e219f0a204247edbf1bf52ed36e157a">
<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="5e219f0a204247edbf1bf52ed36e157a-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="5e219f0a204247edbf1bf52ed36e157a-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="5e219f0a204247edbf1bf52ed36e157a-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