<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@cfe6347f2e754270a3f5ba55ebc962cc" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="4dff59f45adc11ef94f5022c6f26e6af" data-graded="False">
<h2 class="hd hd-2 unit-title">A.1 The Key idea (Pairs)</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@f134b898faa04642aca1b44c16a6b47b">
<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@f134b898faa04642aca1b44c16a6b47b" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="4dff59f45adc11ef94f5022c6f26e6af" data-graded="False">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p><span style="font-family: 'book antiqua', palatino;"><span class="math inline">\(L\)</span> is very simple, but with some ingenuity it can be used to express all sorts of claims about Turing Machines. For instance, there is a sentence of <span class="math inline">\(L\)</span> that is true if and only if a certain Turing Machine computes a particular function. How is that possible? After all, <span class="math inline">\(L\)</span> doesn’t have any symbols that refer to Turing Machines. It’s possible because one can use numbers to <em>code</em> information about Turing Machines. I’ll tell you all about the relevant coding tricks in this section, and we’ll prove the following Lemma:</span></p>
<p style="padding-left: 30px;"><span style="font-family: 'book antiqua', palatino;"><strong>Lemma</strong></span><br /><span style="font-family: 'book antiqua', palatino;"><span class="math inline">\(L\)</span> contains a formula (abbreviated “<span class="math inline">\(\mbox{Halt}(k)\)</span>") which is true if and only if the <span class="math inline">\(k\)</span>th Turing Machine halts on input <span class="math inline">\(k\)</span>.</span></p>
<p></p>
<p><span style="font-family: 'book antiqua', palatino;">Proving this lemma is not hard, but it’s a bit cumbersome.</span></p>
<h4><span style="font-family: 'book antiqua', palatino;">A.1 The Key Idea</span></h4>
<p><span style="font-family: 'book antiqua', palatino;">The key to expressing claims about Turing Machines in <span class="math inline">\(L\)</span> is being able to express claims about <em>sequences</em> in <span class="math inline">\(L\)</span>. Specifically, we need to define a formula “<span class="math inline">\(\mbox{Seq}(c,n,a,i)\)</span>”, which is true if and only if <span class="math inline">\(c\)</span> encodes a sequence of length <span class="math inline">\(n\)</span> of which <span class="math inline">\(a\)</span> is the <span class="math inline">\(i\)</span>-th member. Once we’re equipped with such a formula, it’ll be very easy to use <span class="math inline">\(L\)</span> to say things about Turing Machines because we’ll be able to represent Turing Machines as number-sequences of a particular sort.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">As we go forward, we’ll help ourselves to the abbreviations introduced in Lecture 10.1.1, the most important of which are listed in the figure below. As a further expository aid, I’ll use arbitrary lower-case letters as variables, as I did in the case of “<span class="math inline">\(\mbox{Seq}(c,n,a,i)\)</span>”.</span></p>
<h4><span style="font-family: 'book antiqua', palatino;">Pairs</span></h4>
<p><span style="font-family: 'book antiqua', palatino;">Before plunging into the details, I want you to get a feel for how “<span class="math inline">\(\mbox{Seq}(c,n,a,i)\)</span>” works. We’ll start with the relatively simple task of using <span class="math inline">\(L\)</span> to express claims about 2-sequences (i.e. ordered pairs). In other words: we’ll see how to use a natural number <span class="math inline">\(x_0\)</span> to encode an ordered pair of natural numbers <span class="math inline">\(\langle x_1,x_2\rangle\)</span>. And we’ll see how that coding system can be captured in <span class="math inline">\(L\)</span>. In other words: we’ll see how to write down a sentence of <span class="math inline">\(L\)</span> that is true if and only if <span class="math inline">\(x_0\)</span> encodes the ordered pair <span class="math inline">\(\langle x_1,x_2\rangle.\)</span></span></p>
<p><span style="font-family: 'book antiqua', palatino;">The first step is to specify a coding scheme. which assigns a different natural number to each ordered pair of natural numbers. There are many different such coding schemes, but one I like best is based on the same general idea as the one we used in Lecture 9, when we numbered the Turing Machines. We will code <span class="math inline">\(\langle a, b\rangle\)</span> as <span class="math inline">\(2^{a}\times 3^{b}\)</span>. The reason this coding scheme gives us what we want is that, as we saw in Lecture 9, the Fundamental Theorem of Arithmetic guarantees that it assigns a different natural number to each ordered pair of natural numbers. (The main difference between the current scheme and the scheme we used in Lecture 9 is that in the present context there is no need to add one to the exponents. This causes no ambiguity because we are coding sequences of <em>fixed length</em>, unlike what we did in Lecture 9.)</span></p>
<p><span class="math display" style="font-family: 'book antiqua', palatino;">\[\begin{array}{ccc} \text{Abbreviation} &\text{Read} &\text{Abbreviates} \\ \hline \text{$A \vee B$} & \text{$A$ or $B$} & \text{$\neg(\neg A \ \& \ \neg B)$} \\ \text{$A \supset B$} & \text{if $A$, then $B$} & \text{$\neg A \vee B$} \\ \text{$\exists x_i$} & \text{some number is such that} & \text{$\neg \forall x_i \neg$} \\ \text{$\exists ! x_i$} & \text{there is exactly one number such that} & \text{$\exists x_i (\phi(x_i) \ \& \ \forall x_j (\phi(x_j) \supset x_j = x_i))$} \\ \text{$x_i < x_j$} & \text{$x_i$ is smaller than $x_j$} & \text{\(\exists x_k( (x_j = x_i + x_k) \ \& \ \neg(x_k = 0))\)}\\ \text{$x_i \leq x_j$} & \text{$x_i$ is less than or equal to $x_j$} & \text{\((x_i < x_j \vee x_i = x_j)\)}\\ \text{$x_i | x_j$} & \text{$x_i$ divides $x_j$} & \text{\(\exists x_k (x_k \times x_i = x_j)\)}\\ \text{$\text{Prime}(x_i)$} & \text{$x_i$ is prime} & \text{ \((1< x_i) \ \&\ \forall x_j\forall x_k((x_i = x_j\times x_k)\supset(x_i=x_j\vee x_i=x_k))\)}\\ \end{array}\]</span></p>
<p><span style="font-family: 'book antiqua', palatino;">Let us now see how our coding scheme might be captured within <span class="math inline">\(L\)</span>. What we want is formula “<span class="math inline">\(\mbox{Pair}(x_i,x_j,x_k)\)</span>”, which true if and only if <span class="math inline">\(x_i\)</span> is a code for <span class="math inline">\(\langle x_j,x_k\rangle \)</span>, according to our coding scheme. But this is easily done:<span class="math display">\[\mbox{Pair}(x_i,x_j,x_k) \leftrightarrow_{df} x_i=(2^{x_j}\times 3^{x_k})\]</span></span></p>
<p><span style="font-family: 'book antiqua', palatino;">Now that we have <span class="math inline">\(\mbox{Pair}(x_0,x_1,x_2)\)</span> in place, we can use it as the basis for further notational abbreviations. For example, we can define a formula “<span class="math inline">\(\mbox{First}(x_i,x_j)\)</span>" that is true if and only if <span class="math inline">\(x_i\)</span> codes a pair of which <span class="math inline">\(x_j\)</span> is the first member: <span class="math display">\[\mbox{First}(x_i,x_j) \leftrightarrow_{df} \exists x_k (\mbox{Pair}(x_i,x_j,x_k))\]</span></span></p>
<p></p>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@149674e4dcab49f58e2105c422188c74">
<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@149674e4dcab49f58e2105c422188c74" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="4dff59f45adc11ef94f5022c6f26e6af" data-graded="False">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<h3><span style="font-family: 'book antiqua', palatino;">Video Review: Pairs</span></h3>
<p><span style="font-family: book antiqua,palatino;"><em>Warning:</em> in the video below I use a slightly different coding system to code ordered pairs in \(L\). Instead of using the number \(2^a \times 3^b\) to code the pair \(<a,b>\), as I do in the text, I use the number \(2^{a+1}\times3^{b+1}\).</span></p>
<p><span style="font-family: book antiqua,palatino;">Either coding system is fine, as long as one uses it consistently.</span></p>
<p></p>
</div>
</div>
<div class="vert vert-2" data-id="block-v1:MITx+24.118x+2T2020+type@video+block@5e1b63201ba94865a81999734a305353">
<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@5e1b63201ba94865a81999734a305353" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="4dff59f45adc11ef94f5022c6f26e6af" data-graded="False">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video Review: Pairs</h3>
<div
id="video_5e1b63201ba94865a81999734a305353"
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@5e1b63201ba94865a81999734a305353/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@5e1b63201ba94865a81999734a305353/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@5e1b63201ba94865a81999734a305353/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@5e1b63201ba94865a81999734a305353/handler/transcript/translation/__lang__", "transcriptLanguages": {"en": "English"}, "streams": "1.00:4Ex_8eRaxdo", "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="5e1b63201ba94865a81999734a305353"></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_5e1b63201ba94865a81999734a305353">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_5e1b63201ba94865a81999734a305353">
<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@5e1b63201ba94865a81999734a305353/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@5e1b63201ba94865a81999734a305353/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@23497ba97937402b973becae21ec884b" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="4dff59f45adc11ef94f5022c6f26e6af" data-graded="False">
<h2 class="hd hd-2 unit-title">A.1 The Key Idea (Sequences)</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@8f701ac73427444ab82555eb937d775b">
<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@8f701ac73427444ab82555eb937d775b" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="4dff59f45adc11ef94f5022c6f26e6af" data-graded="False">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<h4><span style="font-family: 'book antiqua', palatino;">Sequences: introduction</span></h4>
<p><span style="font-family: 'book antiqua', palatino;">We have now seen how to use <span class="math inline">\(L\)</span> to talk about sequences of length two. The same technique can be used for sequences of any particular length. So, for instance, one can encode the triple <span class="math inline">\(\langle a,b,c\rangle\)</span> as <span class="math inline">\(2^{a}\times 3^{b}\times 5^{c}\)</span>, and use the formula “<span class="math inline">\(x = 2^{a}\times 3^{b} \times 5^{c}\)</span>” to express the claim that <span class="math inline">\(x\)</span> encodes the triple <span class="math inline">\(a,b,c\)</span>.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">What we need to prove the theorem, however, is a single formula that allows us to talk about sequences of any finite length: we need is a formula “<span class="math inline">\(\mbox{Seq}(c,n,a,i)\)</span>" that is true if and only if <span class="math inline">\(c\)</span> encodes an sequence of length <span class="math inline">\(n\)</span> of which <span class="math inline">\(a\)</span> is the <span class="math inline">\(i\)</span>-th member. The definition of “<span class="math inline">\(\mbox{Seq}(c,n,a,i)\)</span>” is trickier than one might have thought, and I’d like to start by explaining why.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">Why can’t we define “<span class="math inline">\(\mbox{Seq}(c,n,a,i)\)</span>” by using the technique we’ve been using so far? Let’s try, and see what goes wrong. Suppose we code the <span class="math inline">\(n\)</span>-membered sequence <span class="math inline">\(\langle a_1, a_2,\ldots a_n\rangle\)</span> as the number: <span class="math display">\[c=p_1^{a_1}\times p_2^{a_2}\times\ldots\times p_n^{a_n}\]</span> (where <span class="math inline">\(p_1, p_2, \ldots p_n\)</span> are the first <span class="math inline">\(n\)</span> prime numbers).</span></p>
<p><span style="font-family: 'book antiqua', palatino;">We now need to find a formula “<span class="math inline">\(\mbox{Seq}(c,n,a,i)\)</span>” which (relative to this coding method) expresses the claim that the <span class="math inline">\(i\)</span>th member of our (encoded) <span class="math inline">\(n\)</span>-membered sequence <span class="math inline">\(c\)</span> is <span class="math inline">\(a\)</span>, and does so regardless of the value of <span class="math inline">\(n\)</span>. The task would be straightforward if we had a straightforward way of defining a formula “<span class="math inline">\(\mbox{Prime}(p,n)\)</span>” of <span class="math inline">\(L\)</span> which is true if and only if <span class="math inline">\(p\)</span> is the <span class="math inline">\(n\)</span>-th prime number. For then we would be able introduce the following notational abbreviation: <span class="math display">\[\mbox{Seq}(c,n,a,i) \leftrightarrow_{df} \forall x_1 (\mbox{Prime}(x_1,i)\; \supset ((x_1^{a} \, |\, c) \ \& \ \neg(x_1^{a+1}\, |\, c)))\]</span> Unfortunately, defining “<span class="math inline">\(\mbox{Prime}(p,n)\)</span>” turns out to be no easier than defining “<span class="math inline">\(\mbox{Seq}(c,n,a,i)\)</span>”. So we’ll need to follow a different route.</span></p>
<h4><span style="font-family: 'book antiqua', palatino;">Sequences: the coding scheme</span></h4>
<p><span style="font-family: 'book antiqua', palatino;">The problem of defining “<span class="math inline">\(\mbox{Seq}(c,n,a,i)\)</span>” consists of two different two subproblems. The first is to characterize a suitable coding scheme. The second is to identify the specific formula “<span class="math inline">\(\mbox{Seq}(c,n,a,i)\)</span>” of <span class="math inline">\(L\)</span> that will allow us to talk about that coding scheme in <span class="math inline">\(L\)</span>.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">Let us start with the coding scheme. The Fundamental Theorem of Arithmetic allows us to introduce a useful definition. Suppose that <span class="math inline">\(c\)</span> is a natural number, and that its (unique) decomposition into primes is as follows: <span class="math display">\[c = p_1^{e_1} \cdot p_2^{e_2} \cdot p_3^{e_3} \cdot \ldots\]</span> Then we can say that the <em>non-trivial exponents</em> of <span class="math inline">\(c\)</span> are the <span class="math inline">\(e_i\)</span> greater than 0. So, for example, the set of non-trivial exponents of 168 is <span class="math inline">\(\{1,3\}\)</span> because <span class="math inline">\(168 = 2^3 \cdot 3^1 \cdot 7^1\)</span>. (Recall that the set <span class="math inline">\(\{3,1,1\}\)</span> is the same as the set <span class="math inline">\(\{1,3\}\)</span>.)</span></p>
<p><span style="font-family: 'book antiqua', palatino;">The key to our coding scheme is to think of a number as a code for the set of its non-trivial exponents. So, for example, one can think of 168 as a code for the set <span class="math inline">\(\{1,3\}\)</span>, and one can think of the number <span class="math inline">\(5600 = 2^5 \cdot 5^2 \cdot 7^1\)</span> as a code for the set <span class="math inline">\(\{1,2,5\}\)</span>. (Notice, incidentally, that different numbers can code the same set. We have seen, for example, that 168 codes <span class="math inline">\(\{1,3\}\)</span>, but so does 24, since <span class="math inline">\(24 = 2^3 \cdot 3^1\)</span>.)</span></p>
<p><span style="font-family: 'book antiqua', palatino;">We have found a way of using a single number to code a <em>set</em> of numbers. But what we really want is a way of using a single number to code a <em>sequence</em> of numbers. The difference between sets and sequences is that sets are unordered and sequences are ordered. (In general, one can think of a sequence as a total ordering of a set, in the sense of Lecture 2.) Since there are two different ways of totally ordering the set <span class="math inline">\(\{1,3\}\)</span>, this means that <span class="math inline">\(\{1,3\}\)</span> corresponds to two different sequences, <span class="math inline">\(\langle 1,3\rangle \)</span> and <span class="math inline">\(\langle 3,1\rangle \)</span>. So when we think of 168 as a code for the set <span class="math inline">\(\{1,3\}\)</span>, we have not yet linked it to a particular sequence.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">Fortunately, there is an additional trick that can be used to get a single number to code an ordered set of numbers. For suppose that some of <span class="math inline">\(c\)</span>’s non-trivial exponents code ordered pairs, and that each such pair has a different natural number as its first component. Then the first components of the pairs can be used to define an ordering of pairs, and therefore an ordering of the pairs’ second components.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">Here is an example. Suppose that <span class="math inline">\(c\)</span> is the number <span class="math inline">\(2^{2^2 \cdot 3^{17}} \cdot 5^{2^1 \cdot 3^7} \cdot 7^{2^3 \cdot 3^{117}}\)</span>. Then the set of <span class="math inline">\(c\)</span>’s non-trivial exponents is <span class="math inline">\(\{2^2 \cdot 3^{17},2^1 \cdot 3^7,2^3 \cdot 3^{117}\}\)</span>. When we think of these numbers as coding ordered pairs, we get the set <span class="math inline">\(\{\langle 2,17 \rangle, \langle 1,7 \rangle, \langle 3,117 \rangle\}\)</span>. And of course, the first components of the pairs in this set naturally define an ordering of the pairs: <span class="math inline">\(\langle 1,7 \rangle, \langle 2,17 \rangle, \langle 3,117 \rangle\)</span>. This ordering of pairs induces an ordering the pairs’ second components: <span class="math inline">\(7, 17, 117\)</span>. So <span class="math inline">\(c\)</span> can be thought of as coding the three-membered sequence <span class="math inline">\(\langle 7,17,117\rangle\)</span>.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">A more formal version of this basic idea is based on the following definition: <strong><span class="math inline">\(c\)</span> encodes an <span class="math inline">\(n\)</span>-sequence</strong> if and only if for each <span class="math inline">\(i\)</span> <span class="math inline">\((1 \leq i \leq n)\)</span> <span class="math inline">\(c\)</span>’s non-trivial exponents include (the code for) exactly one pair of the form <span class="math inline">\(\langle i,b\rangle\)</span>.</span></p>
<h4><span style="font-family: 'book antiqua', palatino;">Sequences: expressing the coding scheme in L</span></h4>
<p><span style="font-family: 'book antiqua', palatino;">Our coding scheme is now in place. The next step is to define “<span class="math inline">\(\mbox{Seq}(c,n,a,i)\)</span>”, by identifying a formula which is true if and only if <span class="math inline">\(c\)</span> encodes an <span class="math inline">\(n\)</span>-sequence of which the <span class="math inline">\(i\)</span>-th member is <span class="math inline">\(a\)</span>. (All of this, relative to our coding scheme, of course.) We will proceed in two steps. The first step is to introduce a formula “<span class="math inline">\(\mbox{Seq}(c,n)\)</span>”, which is true if and only if <span class="math inline">\(c\)</span> encodes an <span class="math inline">\(n\)</span>-sequence. Then we’ll use “<span class="math inline">\(\mbox{Seq}(c,n)\)</span>” to define “<span class="math inline">\(\mbox{Seq}(c,n,a,i)\)</span>”.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">In light of our definition of “encoding an <span class="math inline">\(n\)</span>-sequence", we want “<span class="math inline">\(\mbox{Seq}(c,n)\)</span>" to be true if and only if: for each <span class="math inline">\(i\)</span> <span class="math inline">\((1 \leq i \leq n)\)</span>, <span class="math inline">\(c\)</span>’s non-trivial exponents include the code for exactly one pair of the form <span class="math inline">\(\langle i,b\rangle\)</span>. Here is one way of doing so: <span class="math display">\[\begin{array}{ccl} \text{Seq}(c,n) &\leftrightarrow_{df} &\forall x_i ((1 \leq x_i \ \& \ x_i \leq n) \supset\\ & & \exists ! x_j (\exists x_k (x_j = 2^{x_i} \times 3^{x_k})\ \& \ \exists x_k (\text{Prime}(x_k) \, \& \, x_k^{x_j} \, |\, c \,\&\, \neg(x_k^{x_j+1} \, |\, c))) \end{array}\]</span></span></p>
<p><span style="font-family: 'book antiqua', palatino;">Now that “<span class="math inline">\(\mbox{Seq}(c,n)\)</span>" is in place, we can use it to characterize “<span class="math inline">\(\mbox{Seq}(c,n,a,i)\)</span>", which should be true if and only if <span class="math inline">\(c\)</span> encodes an <span class="math inline">\(n\)</span>-sequence of which the <span class="math inline">\(i\)</span>-th member is <span class="math inline">\(a\)</span>. Relative to our coding scheme, this will be the case if and only if each of the following three conditions are met:</span></p>
<ul>
<li>
<p><span class="math inline" style="font-family: 'book antiqua', palatino;">\(\mbox{Seq}(c,n)\)</span></p>
</li>
<li>
<p><span style="font-family: 'book antiqua', palatino;"><span class="math inline">\((1 \leq i \ \& \ i\leq n)\)</span>;</span></p>
</li>
<li>
<p><span style="font-family: 'book antiqua', palatino;"><span class="math inline">\(c\)</span>’s non-trivial exponents include a code for <span class="math inline">\(\langle i, a\rangle\)</span>.</span></p>
</li>
</ul>
<p><span style="font-family: 'book antiqua', palatino;">Here is one way of defining “<span class="math inline">\(\mbox{Seq}(c,n,a,i)\)</span>” so that it captures these three conditions: <span class="math display">\[\begin{array}{ccl} \text{Seq}(c,n,a,i) &\leftrightarrow_{df} &\mbox{Seq}(c,n) \ \& \\ & & (1 \leq i \ \& \ i\leq n) \ \&\\ & &\exists x_j \big(\mbox{Prime}(x_j) \ \&\ (x_j^{(2^{i} \times 3^{a})} \, | \, c) \ \& \ \neg(x_j^{(2^{i} \times 3^{a})+1} \, | \, c)\big) \end{array}\]</span></span></p>
<p></p>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+24.118x+2T2020+type@video+block@8c84056877a64740971027f0db38daf8">
<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@8c84056877a64740971027f0db38daf8" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="4dff59f45adc11ef94f5022c6f26e6af" data-graded="False">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video: Sequences</h3>
<div
id="video_8c84056877a64740971027f0db38daf8"
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@8c84056877a64740971027f0db38daf8/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@8c84056877a64740971027f0db38daf8/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@8c84056877a64740971027f0db38daf8/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@8c84056877a64740971027f0db38daf8/handler/transcript/translation/__lang__", "transcriptLanguages": {"en": "English"}, "streams": "1.00:3y2z7s7A--I", "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="8c84056877a64740971027f0db38daf8"></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_8c84056877a64740971027f0db38daf8">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_8c84056877a64740971027f0db38daf8">
<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@8c84056877a64740971027f0db38daf8/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@8c84056877a64740971027f0db38daf8/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@2efacccc9e1144d5888bf699609abac1">
<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@2efacccc9e1144d5888bf699609abac1" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="4dff59f45adc11ef94f5022c6f26e6af" data-graded="False">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_2efacccc9e1144d5888bf699609abac1" class="problems-wrapper" role="group"
aria-labelledby="2efacccc9e1144d5888bf699609abac1-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@2efacccc9e1144d5888bf699609abac1" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@2efacccc9e1144d5888bf699609abac1/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="2efacccc9e1144d5888bf699609abac1-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@2efacccc9e1144d5888bf699609abac1-problem-progress" tabindex="-1">
Problem 1
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@2efacccc9e1144d5888bf699609abac1-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;">Relative to our coding scheme, is it possible for two different numbers to encode the same <span class="math inline">\(n\)</span>-sequence?</span>
</p>
<div class="choicegroup capa_inputtype" id="inputtype_2efacccc9e1144d5888bf699609abac1_2_1">
<fieldset aria-describedby="status_2efacccc9e1144d5888bf699609abac1_2_1">
<div class="field">
<input type="radio" name="input_2efacccc9e1144d5888bf699609abac1_2_1" id="input_2efacccc9e1144d5888bf699609abac1_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="2efacccc9e1144d5888bf699609abac1_2_1-choice_0-label" for="input_2efacccc9e1144d5888bf699609abac1_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_2efacccc9e1144d5888bf699609abac1_2_1">
<span style="font-family: 'book antiqua', palatino;">Yes</span>
</label>
</div>
<div class="field">
<input type="radio" name="input_2efacccc9e1144d5888bf699609abac1_2_1" id="input_2efacccc9e1144d5888bf699609abac1_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="2efacccc9e1144d5888bf699609abac1_2_1-choice_1-label" for="input_2efacccc9e1144d5888bf699609abac1_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_2efacccc9e1144d5888bf699609abac1_2_1">
<span style="font-family: 'book antiqua', palatino;">No</span>
</label>
</div>
<span id="answer_2efacccc9e1144d5888bf699609abac1_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_2efacccc9e1144d5888bf699609abac1_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_2efacccc9e1144d5888bf699609abac1_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_2efacccc9e1144d5888bf699609abac1" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_2efacccc9e1144d5888bf699609abac1">
<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="2efacccc9e1144d5888bf699609abac1-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="2efacccc9e1144d5888bf699609abac1-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="2efacccc9e1144d5888bf699609abac1-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@5486f5d4bcee42afa1dea6858cc0e7c3">
<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@5486f5d4bcee42afa1dea6858cc0e7c3" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="4dff59f45adc11ef94f5022c6f26e6af" data-graded="False">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_5486f5d4bcee42afa1dea6858cc0e7c3" class="problems-wrapper" role="group"
aria-labelledby="5486f5d4bcee42afa1dea6858cc0e7c3-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@5486f5d4bcee42afa1dea6858cc0e7c3" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@5486f5d4bcee42afa1dea6858cc0e7c3/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="5486f5d4bcee42afa1dea6858cc0e7c3-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@5486f5d4bcee42afa1dea6858cc0e7c3-problem-progress" tabindex="-1">
Problem 2
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@5486f5d4bcee42afa1dea6858cc0e7c3-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;">Relative to our coding scheme, is it possible for a single number to encode an <span class="math inline">\(n\)</span>-sequence and an <span class="math inline">\(m\)</span>-sequence for <span class="math inline">\(n\neq m\)</span>?</span>
</p>
<div class="choicegroup capa_inputtype" id="inputtype_5486f5d4bcee42afa1dea6858cc0e7c3_2_1">
<fieldset aria-describedby="status_5486f5d4bcee42afa1dea6858cc0e7c3_2_1">
<div class="field">
<input type="radio" name="input_5486f5d4bcee42afa1dea6858cc0e7c3_2_1" id="input_5486f5d4bcee42afa1dea6858cc0e7c3_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="5486f5d4bcee42afa1dea6858cc0e7c3_2_1-choice_0-label" for="input_5486f5d4bcee42afa1dea6858cc0e7c3_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_5486f5d4bcee42afa1dea6858cc0e7c3_2_1">
<span style="font-family: 'book antiqua', palatino;">Yes</span>
</label>
</div>
<div class="field">
<input type="radio" name="input_5486f5d4bcee42afa1dea6858cc0e7c3_2_1" id="input_5486f5d4bcee42afa1dea6858cc0e7c3_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="5486f5d4bcee42afa1dea6858cc0e7c3_2_1-choice_1-label" for="input_5486f5d4bcee42afa1dea6858cc0e7c3_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_5486f5d4bcee42afa1dea6858cc0e7c3_2_1">
<span style="font-family: 'book antiqua', palatino;">No</span>
</label>
</div>
<span id="answer_5486f5d4bcee42afa1dea6858cc0e7c3_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_5486f5d4bcee42afa1dea6858cc0e7c3_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_5486f5d4bcee42afa1dea6858cc0e7c3_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_5486f5d4bcee42afa1dea6858cc0e7c3" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_5486f5d4bcee42afa1dea6858cc0e7c3">
<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="5486f5d4bcee42afa1dea6858cc0e7c3-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="5486f5d4bcee42afa1dea6858cc0e7c3-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="5486f5d4bcee42afa1dea6858cc0e7c3-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@486d816a0b9f4f2da0354962438cb65a">
<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@486d816a0b9f4f2da0354962438cb65a" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="4dff59f45adc11ef94f5022c6f26e6af" data-graded="False">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_486d816a0b9f4f2da0354962438cb65a" class="problems-wrapper" role="group"
aria-labelledby="486d816a0b9f4f2da0354962438cb65a-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@486d816a0b9f4f2da0354962438cb65a" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@486d816a0b9f4f2da0354962438cb65a/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="486d816a0b9f4f2da0354962438cb65a-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@486d816a0b9f4f2da0354962438cb65a-problem-progress" tabindex="-1">
Checkboxes
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@486d816a0b9f4f2da0354962438cb65a-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;">Use &#8220;<span class="math inline">\(\mbox{Seq}(c,n,a,i)\)</span>&#8221; to define a predicate &#8220;<span class="math inline">\(\text{Prime}(p,n)\)</span>&#8221; which is true if and only if <span class="math inline">\(p\)</span> is the <span class="math inline">\(n\)</span>th prime number (where <span class="math inline">\(1 \leq n\)</span>).</span>
</p>
<div class="choicegroup capa_inputtype" id="inputtype_486d816a0b9f4f2da0354962438cb65a_2_1">
<fieldset aria-describedby="status_486d816a0b9f4f2da0354962438cb65a_2_1">
<div class="field">
<input type="checkbox" name="input_486d816a0b9f4f2da0354962438cb65a_2_1[]" id="input_486d816a0b9f4f2da0354962438cb65a_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="486d816a0b9f4f2da0354962438cb65a_2_1-choice_0-label" for="input_486d816a0b9f4f2da0354962438cb65a_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_486d816a0b9f4f2da0354962438cb65a_2_1">
<span style="font-family: 'book antiqua', palatino;">Done</span>
</label>
</div>
<span id="answer_486d816a0b9f4f2da0354962438cb65a_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_486d816a0b9f4f2da0354962438cb65a_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_486d816a0b9f4f2da0354962438cb65a_solution_1"/>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Checkboxes" />
<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_486d816a0b9f4f2da0354962438cb65a" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_486d816a0b9f4f2da0354962438cb65a">
<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="486d816a0b9f4f2da0354962438cb65a-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="486d816a0b9f4f2da0354962438cb65a-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="486d816a0b9f4f2da0354962438cb65a-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-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@17794e055ce042c2ad78df984c2c2ec0" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="4dff59f45adc11ef94f5022c6f26e6af" data-graded="False">
<h2 class="hd hd-2 unit-title">A.2 Describing Turing Machines in L</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@2844740f80634de5bc0d04005e8c3e28">
<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@2844740f80634de5bc0d04005e8c3e28" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="4dff59f45adc11ef94f5022c6f26e6af" data-graded="False">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p><span style="font-family: 'book antiqua', palatino;">In the previous subsection we introduce a coding scheme, and defined two important pieces of notation that pertain to that scheme:</span></p>
<ul>
<li>
<p><span style="font-family: 'book antiqua', palatino;">“<span class="math inline">\(\mbox{Seq}(c,n)\)</span>”, which is true if and only if <span class="math inline">\(c\)</span> codes a sequence of length <span class="math inline">\(n\)</span>.</span></p>
</li>
<li>
<p><span style="font-family: 'book antiqua', palatino;">“<span class="math inline">\(\mbox{Seq}(c,n,a,i)\)</span>”, which is true if and only if <span class="math inline">\(c\)</span> codes a sequence of length <span class="math inline">\(n\)</span> of which <span class="math inline">\(a\)</span> is the <span class="math inline">\(i\)</span>th component.</span></p>
</li>
</ul>
<p><span style="font-family: 'book antiqua', palatino;">The hardest part of proving our Lemma is defining these two pieces of notation. Now that they are in place, we’ll find it easy to express claims about Turing Machines in <span class="math inline">\(L\)</span>. (To keep things simple, I will assume that we are working with one-symbol Turing Machines, in which anything printed on the tape is either a one or a blank.)</span></p>
<h4><span style="font-family: 'book antiqua', palatino;">Command-lines</span></h4>
<p><span style="font-family: 'book antiqua', palatino;">Recall that each command-line of a Turing Machine is a sequence of five symbols, corresponding to the following parameters: <span class="math display">\[\langle \text{current state}\rangle \langle\text{current symbol}\rangle \langle\text{new symbol}\rangle \langle\text{direction}\rangle \langle\text{new state}\rangle\]</span> In Lecture 9 we saw that each Turing Machine command-line can be represented as a sequence of five <em>numbers</em> with the following features:</span></p>
<ul>
<li>
<p><span style="font-family: 'book antiqua', palatino;">The first and last members of the sequence are arbitrary natural numbers (since they represent possible Turing-machine states).</span></p>
</li>
<li>
<p><span style="font-family: 'book antiqua', palatino;">The second and third members of the sequence are natural numbers in <span class="math inline">\(\{0,1\}\)</span> (since they represent symbols, and the only admissible symbols are ones and blanks).</span></p>
</li>
<li>
<p><span style="font-family: 'book antiqua', palatino;">The fourth member of the sequence is a natural number in <span class="math inline">\(\{0,1,2\}\)</span> (which represents “right”, “stay put” and “left”, respectively).</span></p>
</li>
</ul>
<p><span style="font-family: 'book antiqua', palatino;">It is easy to define a formula “<span class="math inline">\(\text{Command}(x_i)\)</span>”, which is true if and only if <span class="math inline">\(x_i\)</span> represents a 5-sequence that corresponds to a valid command-line: <span class="math display">\[\begin{array}{ccl} \text{Command}(x_i) &\leftrightarrow_{df} &\forall x_k (\mbox{Seq}(x_i,5,x_k,2) \supset x_k \leq 1) \ \& \\ & &\forall x_k (\mbox{Seq}(x_i,5,x_k,3) \supset x_k \leq 1) \ \& \\ & &\forall x_k (\mbox{Seq}(x_i,5,x_k,4) \supset x_k \leq 2) \end{array}\]</span></span></p>
<h4><span style="font-family: 'book antiqua', palatino;">Programs</span></h4>
<p><span style="font-family: 'book antiqua', palatino;">A Turing Machine program is just a sequence of command lines. Since each command line can be coded as a single number, an entire Turing Machine program can be coded as a sequence of numbers.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">It is easy to define a formula“<span class="math inline">\(\text{Program}(s,n)\)</span>”, which is true if and only if <span class="math inline">\(s\)</span> represents a sequence of <span class="math inline">\(n\)</span> valid Turing Machine command-lines:</span></p>
<p><span class="math display" style="font-family: 'book antiqua', palatino;">\[\begin{array}{ccl} \text{Program}(s,n) &\leftrightarrow_{df} &\text{Seq}(s,n) \ \& \\ & &\forall x_j \forall x_k ((1\leq x_j \, \&\, x_j \leq n \, \&\, \text{Seq}(s,n,x_k,x_j)) \supset \text{Command}(x_k)) \end{array}\]</span></p>
<h4></h4>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+24.118x+2T2020+type@video+block@3b6fa8ee98ad475ba033d1f9ae16d487">
<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@3b6fa8ee98ad475ba033d1f9ae16d487" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="4dff59f45adc11ef94f5022c6f26e6af" data-graded="False">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video Review: Sequences and Programs</h3>
<div
id="video_3b6fa8ee98ad475ba033d1f9ae16d487"
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@3b6fa8ee98ad475ba033d1f9ae16d487/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@3b6fa8ee98ad475ba033d1f9ae16d487/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@3b6fa8ee98ad475ba033d1f9ae16d487/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@3b6fa8ee98ad475ba033d1f9ae16d487/handler/transcript/translation/__lang__", "transcriptLanguages": {"en": "English"}, "streams": "1.00:hWvbAl5-UVo", "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="3b6fa8ee98ad475ba033d1f9ae16d487"></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_3b6fa8ee98ad475ba033d1f9ae16d487">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_3b6fa8ee98ad475ba033d1f9ae16d487">
<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@3b6fa8ee98ad475ba033d1f9ae16d487/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@3b6fa8ee98ad475ba033d1f9ae16d487/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@html+block@13d8e67f318840329911020d5a00b439">
<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@13d8e67f318840329911020d5a00b439" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="4dff59f45adc11ef94f5022c6f26e6af" data-graded="False">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<h4><span style="font-family: 'book antiqua', palatino;">The Tape and reader</span></h4>
<p><span style="font-family: 'book antiqua', palatino;">How might one describe the contents of a Turing Machine’s tape in <span class="math inline">\(L\)</span>? Let me start with a couple of qualifications:</span></p>
<ul>
<li>
<p><span style="font-family: 'book antiqua', palatino;">We will focus our attention on tapes that contain at most finitely many non-blanks. This is warranted because we are only interested in the behavior of Turing Machines that start out with a finite input, and such machines must have at most finitely many non-blanks at each stage of their running processes.</span></p>
</li>
<li>
<p><span style="font-family: 'book antiqua', palatino;">When we introduced Turing Machines in Lecture 9, we stipulated that the tape was to be infinite in both directions. Here, however, we will simplify matters by assuming that tapes are only infinite to the right. But this is a harmless simplification in the present context. For, as I asked you to verify in Lecture 9, any function that can be computed by a Turing Machine with a tape that is infinite in both directions can also be computed on a Turing Machine with a tape that is only infinite in one direction.</span></p>
</li>
</ul>
<p><span style="font-family: 'book antiqua', palatino;">With these qualifications in place, the contents of a tape can be coded as an <span class="math inline">\(n\)</span>-sequence of ones and zeroes, with ones representing ones, and zeroes representing blanks. The order of the <span class="math inline">\(n\)</span>-sequence corresponds to the order of cells on the tape, going from left to right, so that the first member of the sequence represents the contents of the left-most cell on the tape, and the <span class="math inline">\(n\)</span>th member of the sequence represents the contents of right-most non-blank cell on the tape.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">It is straightforward to define a formula“<span class="math inline">\(\text{Tape}(s,n)\)</span>”, which is true if and only if <span class="math inline">\(s\)</span> represents a sequence of <span class="math inline">\(n\)</span> zeroes and ones that ends with a one:</span></p>
<p><span style="font-family: 'book antiqua', palatino;"><span class="math display">\[\begin{array}{cccl} \text{Tape}(s,n) &\leftrightarrow_{df} &1 \leq n \ \supset \\ & & &(\text{Seq}(s,n,1,n) \ \&\\ & & &\forall x_i ((1 \leq x_i \,\&\, x_i < n) \supset (\text{Seq}(s,n,0,x_i) \vee \text{Seq}(s,n,1,x_i))))\\ \end{array}\]</span> Since we are focusing on Turing Machines that are only infinite to the right, we can represent the position of the machine’s reader as a positive natural number, and say that the reader is at position <span class="math inline">\(n\)</span> when it is positioned at the <span class="math inline">\(n\)</span>th cell from the left.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">When the reader is at position <span class="math inline">\(r\)</span> of tape <span class="math inline">\(t\)</span>, we’ll use the formula “<span class="math inline">\(\text{ReadSymbol}(y,r,t,n)\)</span>” to keep track of the symbol on which the reader is positioned. More specifically, we want “<span class="math inline">\(\text{ReadSymb}(y,r,t,n)\)</span>” to be true if and only if the symbol coded by <span class="math inline">\(y\)</span> occurs at the <span class="math inline">\(r\)</span>th position of the tape coded by <span class="math inline">\(t\)</span> (whose right-most non-blank is on the <span class="math inline">\(n\)</span>th cell to the right). Here is one way of doing so: <span class="math display">\[\begin{array}{ccl} \text{ReadSymb}(y,r,t,n) &\leftrightarrow_{df} &(r \leq n \supset \text{Seq}(t,n,y,r)) \ \&\\ & &(n < r \supset y = 0) \end{array}\]</span></span></p>
</div>
</div>
<div class="vert vert-3" data-id="block-v1:MITx+24.118x+2T2020+type@video+block@5b3cb6d14bb3485491422aa1d708c9b6">
<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@5b3cb6d14bb3485491422aa1d708c9b6" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="4dff59f45adc11ef94f5022c6f26e6af" data-graded="False">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video Review: Coding the Tape</h3>
<div
id="video_5b3cb6d14bb3485491422aa1d708c9b6"
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@5b3cb6d14bb3485491422aa1d708c9b6/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@5b3cb6d14bb3485491422aa1d708c9b6/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@5b3cb6d14bb3485491422aa1d708c9b6/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@5b3cb6d14bb3485491422aa1d708c9b6/handler/transcript/translation/__lang__", "transcriptLanguages": {"en": "English"}, "streams": "1.00:0Z6-kArS1wg", "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="5b3cb6d14bb3485491422aa1d708c9b6"></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_5b3cb6d14bb3485491422aa1d708c9b6">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_5b3cb6d14bb3485491422aa1d708c9b6">
<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@5b3cb6d14bb3485491422aa1d708c9b6/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@5b3cb6d14bb3485491422aa1d708c9b6/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@7ef1ff4b5e034daa9f064fef4647677c">
<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@7ef1ff4b5e034daa9f064fef4647677c" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="4dff59f45adc11ef94f5022c6f26e6af" data-graded="False">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_7ef1ff4b5e034daa9f064fef4647677c" class="problems-wrapper" role="group"
aria-labelledby="7ef1ff4b5e034daa9f064fef4647677c-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@7ef1ff4b5e034daa9f064fef4647677c" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@7ef1ff4b5e034daa9f064fef4647677c/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="7ef1ff4b5e034daa9f064fef4647677c-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@7ef1ff4b5e034daa9f064fef4647677c-problem-progress" tabindex="-1">
Problem 1
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@7ef1ff4b5e034daa9f064fef4647677c-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;">In the previous section we introduced a coding scheme that allows us to encode a Turing Machine&#8217;s program as a unique natural number. In Lecture 9 we introduced a different coding system to do the same thing. (The reason the coding systems are different is that they are optimized for different things. In Lecture 9 we were aiming for a coding scheme that was as simple as possible. In the present context we&#8217;re aiming for a coding scheme that can be perspicuously represented within <span class="math inline">\(L\)</span>.)</span>
</p>
<p>
<span style="font-family: 'book antiqua', palatino;">Use the formula &#8220;<span class="math inline">\(\text{Prime}(p,n)\)</span>&#8221;, which you were asked to define in Section 9, to define a formula &#8220;<span class="math inline">\(\text{Code}(p,n,k)\)</span>&#8221;, which is true if and only if <span class="math inline">\(p\)</span> codes a Turing Machine of length <span class="math inline">\(n\)</span> (relative to the coding scheme of the present section) which is coded by <span class="math inline">\(k\)</span> (relative to the coding scheme of Lecture 9).</span>
</p>
<div class="choicegroup capa_inputtype" id="inputtype_7ef1ff4b5e034daa9f064fef4647677c_2_1">
<fieldset aria-describedby="status_7ef1ff4b5e034daa9f064fef4647677c_2_1">
<div class="field">
<input type="checkbox" name="input_7ef1ff4b5e034daa9f064fef4647677c_2_1[]" id="input_7ef1ff4b5e034daa9f064fef4647677c_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="7ef1ff4b5e034daa9f064fef4647677c_2_1-choice_0-label" for="input_7ef1ff4b5e034daa9f064fef4647677c_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_7ef1ff4b5e034daa9f064fef4647677c_2_1">
<span style="font-family: 'book antiqua', palatino;">Done</span>
</label>
</div>
<span id="answer_7ef1ff4b5e034daa9f064fef4647677c_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_7ef1ff4b5e034daa9f064fef4647677c_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_7ef1ff4b5e034daa9f064fef4647677c_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_7ef1ff4b5e034daa9f064fef4647677c" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_7ef1ff4b5e034daa9f064fef4647677c">
<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="7ef1ff4b5e034daa9f064fef4647677c-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="7ef1ff4b5e034daa9f064fef4647677c-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="7ef1ff4b5e034daa9f064fef4647677c-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-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@5b732b07eae84acaaa54837432450825" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="4dff59f45adc11ef94f5022c6f26e6af" data-graded="False">
<h2 class="hd hd-2 unit-title">A.3 Describing the workings of a Turing Machine in L</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@c4685e93f88c4f28bf51825df20550ea">
<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@c4685e93f88c4f28bf51825df20550ea" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="4dff59f45adc11ef94f5022c6f26e6af" data-graded="False">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p><span style="font-family: 'book antiqua', palatino;">We are now ready to bring together the separate pieces we have been working on, and start characterizing the running process of a Turing Machine. The first step is to define a formula “<span class="math inline">\(\text{Status}(p,n,s,t,m,r)\)</span>” which expresses the thought that:</span></p>
<ul>
<li>
<p><span style="font-family: 'book antiqua', palatino;"><span class="math inline">\(\text{Program}(p,n)\)</span> (i.e. <span class="math inline">\(p\)</span> encodes a valid Turing Machine program consisting of <span class="math inline">\(n\)</span> command lines);</span></p>
</li>
<li>
<p><span style="font-family: 'book antiqua', palatino;"><span class="math inline">\(s\)</span> is an arbitrary number, which will be used to represent our Turing Machine’s current state;</span></p>
</li>
<li>
<p><span style="font-family: 'book antiqua', palatino;"><span class="math inline">\(\mbox{Tape}(t,m)\)</span> (i.e. <span class="math inline">\(t\)</span> encodes the contents of a valid Turing Machine tape, whose right-most non-blank is at the <span class="math inline">\(m\)</span>th cell); and</span></p>
</li>
<li>
<p><span style="font-family: 'book antiqua', palatino;"><span class="math inline">\(r\)</span> is a positive number, which is used to represent a position of the reader on the tape.</span></p>
</li>
</ul>
<p><span style="font-family: 'book antiqua', palatino;">In other words: “<span class="math inline">\(\text{Status}(p,n,s,t,m,r)\)</span>” uses <span class="math inline">\(\langle p,n,s,t,m,r\rangle\)</span> to represent the status that a valid Turing Machine might have at a particular moment in time. Here is one way of defining it: <span class="math display">\[\begin{array}{ccl} \text{Status}(p,n,s,t,m,r) &\leftrightarrow_{df} & \text{Program}(p,n) \ \&\ \text{Tape}(t,m)) \ \&\ 1 \leq r \end{array}\]</span></span></p>
<p></p>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+24.118x+2T2020+type@video+block@51da4c75ad7b41e08766fcbfcd5d77c9">
<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@51da4c75ad7b41e08766fcbfcd5d77c9" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="4dff59f45adc11ef94f5022c6f26e6af" data-graded="False">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video Review: Turing Machine Moments</h3>
<div
id="video_51da4c75ad7b41e08766fcbfcd5d77c9"
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@51da4c75ad7b41e08766fcbfcd5d77c9/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@51da4c75ad7b41e08766fcbfcd5d77c9/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@51da4c75ad7b41e08766fcbfcd5d77c9/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@51da4c75ad7b41e08766fcbfcd5d77c9/handler/transcript/translation/__lang__", "transcriptLanguages": {"en": "English"}, "streams": "1.00:9LLDqVmk7BQ", "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="51da4c75ad7b41e08766fcbfcd5d77c9"></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_51da4c75ad7b41e08766fcbfcd5d77c9">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_51da4c75ad7b41e08766fcbfcd5d77c9">
<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@51da4c75ad7b41e08766fcbfcd5d77c9/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@51da4c75ad7b41e08766fcbfcd5d77c9/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@html+block@53a4d7284bcf4cd291fe39adc68798f0">
<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@53a4d7284bcf4cd291fe39adc68798f0" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="4dff59f45adc11ef94f5022c6f26e6af" data-graded="False">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<h4><span style="font-family: 'book antiqua', palatino;">Initializing</span></h4>
<p><span style="font-family: 'book antiqua', palatino;">Now that we are able to represent the status of a Turing Machine, we are in a position to define a formula “<span class="math inline">\(\text{Initial}(k,i,p,n,s,t,m,r)\)</span>”, which is true if and only if <span class="math inline">\(\langle p,n,s,t,m,r\rangle\)</span> represents the status of the <span class="math inline">\(k\)</span>th Turing Machine at the moment in which it is initialized on input <span class="math inline">\(i\)</span>. (When I speak of the <span class="math inline">\(k\)</span>th Turing Machine here, I have in mind the coding system of Chapter 9. We’ll keep track of this coding scheme by using the formula “<span class="math inline">\(\text{Code}(p,n,k)\)</span>”, which I asked you to define in an exercise above.)</span></p>
<p><span style="font-family: 'book antiqua', palatino;">Formally speaking, we want “<span class="math inline">\(\text{Initial}(k,i,p,n,s,t,m,r)\)</span>” to be true if and only if:</span></p>
<ul>
<li>
<p><span style="font-family: 'book antiqua', palatino;"><span class="math inline">\(\text{Status}(p,n,s,t,m,r)\)</span> (i.e. <span class="math inline">\(\langle p,n,s,t,m,r\rangle\)</span> represents the status of a valid Turing Machine);</span></p>
</li>
<li>
<p><span style="font-family: 'book antiqua', palatino;"><span class="math inline">\(\text{Code}(p,n,k)\)</span> (i.e. the <span class="math inline">\(k\)</span>th Turing machine has program <span class="math inline">\(p\)</span> of length <span class="math inline">\(n\)</span>);</span></p>
</li>
<li>
<p><span style="font-family: 'book antiqua', palatino;"><span class="math inline">\(s = 0\)</span> (i.e. the machine is in state 0);</span></p>
</li>
<li>
<p><span style="font-family: 'book antiqua', palatino;"><span class="math inline">\(t\)</span> is a sequence of <span class="math inline">\(m\)</span> ones (i.e. the tape begins with a sequence of <span class="math inline">\(m\)</span> ones, and is otherwise blank);</span></p>
</li>
<li>
<p><span style="font-family: 'book antiqua', palatino;"><span class="math inline">\(r = 1\)</span> (i.e. the reader is positioned at the left-most cell of the tape).</span></p>
</li>
</ul>
<p><span style="font-family: 'book antiqua', palatino;">Here is one way of doing so: <span class="math display">\[\begin{array}{ccl} \text{Initial}(k,i,p,n,s,t,m,r) &\leftrightarrow_{df} & \text{Status}(p,n,s,t,m,r) \ \& \ \text{Code}(p,n,k) \ \&\ s = 0 \ \& \\ & & \forall j ((i \leq j \,\&\, j \leq m) \supset \text{Seq}(t,m,1,j)) \ \& \ r = 1 \end{array}\]</span> With “<span class="math inline">\(\text{Initial}(k,i,p,n,s,t,m,r)\)</span>” in place, it is easy to define a formula “<span class="math inline">\(\text{Initial}(k,i,a)\)</span>” which is true if and only if <span class="math inline">\(a\)</span> codes a sequence <span class="math inline">\(\langle p,n,s,t,m,r\rangle\)</span> such that <span class="math inline">\(\text{Initial}(k,i,p,n,s,t,m,r)\)</span>:</span></p>
<p><span class="math display" style="font-family: 'book antiqua', palatino;">\[\begin{array}{ccl} \text{Initial}(k,i,a) &\leftrightarrow_{df} &\exists p \exists n \exists t \exists m (\text{Seq}(a,5,p,1) \ \& \ \text{Seq}(a,5,n,2) \ \& \ \text{Seq}(a,5,0,3) \ \& \\ & &\hspace{20mm} \text{Seq}(a,5,t,4) \ \& \ \text{Seq}(a,5,m,5) \ \& \ \text{Seq}(a,5,1,6) \ \& \\ & &\hspace{20mm} \text{Initial}(k,i,p,n,0,t,m,1)) \end{array}\]</span></p>
<p></p>
</div>
</div>
<div class="vert vert-3" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@2a68be82017849d697e6a33b8b0c48b4">
<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@2a68be82017849d697e6a33b8b0c48b4" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="4dff59f45adc11ef94f5022c6f26e6af" data-graded="False">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<h4><span style="font-family: 'book antiqua', palatino;">Halting</span></h4>
<p><span style="font-family: 'book antiqua', palatino;">The next step is to characterize a formula expressing the thought that a Turing Machine has reached its halting state. More specifically, we will define a formula “<span class="math inline">\(\text{Halted}(p,n,s,t,m,r)\)</span>”, which is true if and only if program <span class="math inline">\(p\)</span> (with <span class="math inline">\(n\)</span> command-lines) contains no command-line whose <span class="math inline">\(\langle\text{current state}\rangle\)</span> parameter is filled by <span class="math inline">\(s\)</span> and whose <span class="math inline">\(\langle\text{current symbol}\rangle\)</span> parameter is filled by the symbol occurring at the <span class="math inline">\(r\)</span>th position of the tape coded by <span class="math inline">\(t\)</span> (whose right-most non-blank is on the <span class="math inline">\(m\)</span>th cell to the right). </span></p>
<p><span style="font-family: 'book antiqua', palatino;">Here is one way of doing so: <span class="math display">\[\begin{array}{l} \text{Halted}(p,n,s,t,m,r) \leftrightarrow_{df} \text{ReadSymb}(y,r,t,m) \ \& \\ \hspace{20mm} \forall i \, \forall l \, \forall s' \,\forall y' ((1 \leq i \ \&\ i \leq n \, \& \,\text{Seq}(p,n,l,i) \, \& \,\text{Seq}(l,5,s',1) \,\& \,\text{Seq}(l,5,y',2)) \supset\\ \hspace{115mm} (\neg(s = s') \vee \neg(y = y'))) \end{array}\]</span> With “<span class="math inline">\(\text{Halted}(p,n,s,t,m,r)\)</span>” in place, it is easy to define a formula “<span class="math inline">\(\text{Halted}(a)\)</span>” which is true if and only if <span class="math inline">\(a\)</span> codes a sequence <span class="math inline">\(\langle p,n,s,t,m,r\rangle\)</span> such that <span class="math inline">\(\text{Halted}(p,n,s,t,m,r)\)</span>: <span class="math display">\[\begin{array}{ccl} \text{Halted}(a) &\leftrightarrow_{df} &\exists p \exists n \exists s \exists t \exists m \exists r (\text{Seq}(a,5,p,1) \ \& \ \text{Seq}(a,5,n,2) \ \& \ \text{Seq}(a,5,s,3) \ \& \\ & &\hspace{30mm} \text{Seq}(a,5,t,4) \ \& \ \text{Seq}(a,5,m,5) \ \& \ \text{Seq}(a,5,r,6) \ \& \\ & &\hspace{30mm} \text{Halted}(p,n,s,t,m,r)) \end{array}\]</span></span></p>
<p></p>
</div>
</div>
<div class="vert vert-4" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@6c0b9597cb804be7abdffdb822037486">
<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@6c0b9597cb804be7abdffdb822037486" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="4dff59f45adc11ef94f5022c6f26e6af" data-graded="False">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<h4><span style="font-family: 'book antiqua', palatino;">Steps</span></h4>
<p><span style="font-family: 'book antiqua', palatino;">We are now ready to start representing the transitions in the status of a Turing Machine as it goes through each step of its running process. The first thing we need to do is find a way of expressing claims about what a Turing Machine is programmed to do when it finds itself reading a particular symbol in a particular state. More specifically, we need a formula “<span class="math inline">\(\text{FirstLine}(p,n,s,y,y',d,s')\)</span>”, which is true if and only if the first command-line in program <span class="math inline">\(p\)</span> (of length <span class="math inline">\(n\)</span>) that has <span class="math inline">\(s\)</span> as its <span class="math inline">\(\langle\text{Current State}\rangle\)</span> and <span class="math inline">\(y\)</span> as its <span class="math inline">\(\langle\text{Current Symbol}\rangle\)</span> is such that:</span></p>
<ul>
<li>
<p><span style="font-family: 'book antiqua', palatino;">it has <span class="math inline">\(y'\)</span> as <span class="math inline">\(\langle\text{New Symbol}\rangle\)</span>;</span></p>
</li>
<li>
<p><span style="font-family: 'book antiqua', palatino;">it has <span class="math inline">\(d\)</span> as <span class="math inline">\(\langle\text{direction}\rangle\)</span>; and</span></p>
</li>
<li>
<p><span style="font-family: 'book antiqua', palatino;">it has <span class="math inline">\(s'\)</span> as <span class="math inline">\(\langle\text{New State}\rangle\)</span>.</span></p>
</li>
</ul>
<p><span style="font-family: 'book antiqua', palatino;">Here is one way of defining “<span class="math inline">\(\text{FirstLine}(p,n,s,y,y',d,s')\)</span>”: <span class="math display">\[\begin{array}{l} \text{FirstLine}(p,n,s,y,y',d,s') \leftrightarrow_{df} \\ \quad \exists i \,\exists l \, (1 \leq i \, \&\, i \leq n \ \& \ \text{Seq}(p,n,l,i) \ \& \ \text{Seq}(l,5,s,1) \ \& \ \text{Seq}(l,5,y,2) \ \& \\ \quad \quad \quad \quad \text{Seq}(l,5,y',3) \ \& \text{Seq}(l,5,d,4) \ \& \text{Seq}(l,5,s',5) \ \& \\ \quad \quad \quad \quad \forall j \forall k ((1 \leq j \, \&\, j \leq n \ \& \ \text{Seq}(p,n,k,j) \ \& \ \text{Seq}(k,5,s,1) \ \& \ \text{Seq}(k,5,y,2)) \supset i \leq j)) \end{array}\]</span> We are now in a position to define a formula <span class="math inline">\(\mbox{Step}(p,n,s,t,m,r,s',t',m',r')\)</span> which is true if and only if: a Turing Machine with the status represented by <span class="math inline">\(\langle p,n,s,t,m,r\rangle\)</span> comes to have the status represented by <span class="math inline">\(\langle p,n,s',t',m',r'\rangle\)</span>, after going through one step of its running process. This idea can be captured formally by combining the following two claims:</span></p>
<ul>
<li>
<p><span style="font-family: 'book antiqua', palatino;">First, the claim that the machine’s tape remains unchanged, with the possible exception of the <span class="math inline">\(r\)</span>th cell (which is the cell at which the reader is positioned when the machine is in status <span class="math inline">\(\langle p,n,s,t,m,r\rangle\)</span>).</span></p>
</li>
<li>
<p><span style="font-family: 'book antiqua', palatino;">Second, the claim that the state of the machine, the symbol at the <span class="math inline">\(r\)</span>th position of the tape and the position of the reader all transition in accordance with the program (of length <span class="math inline">\(n\)</span>) represented by <span class="math inline">\(p\)</span>. This can be expressed in <span class="math inline">\(L\)</span> using “<span class="math inline">\(\text{FirstLine}(p,n,s,y,y',d,s')\)</span>", where <span class="math inline">\(y\)</span> is the “old symbol” at position <span class="math inline">\(r\)</span> (i.e. <span class="math inline">\(\text{ReadSymb}(y,r,t,m)\)</span>), <span class="math inline">\(y'\)</span> is the “new symbol” at position <span class="math inline">\(r\)</span> (i.e. <span class="math inline">\(\text{ReadSymb}(y',r,t',m')\)</span>), and <span class="math inline">\(d\)</span> corresponds to the direction that the reader would need to move in to get from its position on the tape according to the “old status" to its position of the tape according to the “new status". Formally, <span class="math inline">\(d\)</span> can be defined as <span class="math inline">\((r-r')+1\)</span>, since the coding system of Chapter 9 is based on the following conventions: <span class="math display">\[\begin{array}{ccc} \text{``r''} &\rightarrow &\text{``0''}\\ \text{``$*$''} &\rightarrow &\text{``1''}\\ \text{``l''} &\rightarrow &\text{``2''} \end{array}\]</span></span></p>
</li>
</ul>
<p><span style="font-family: 'book antiqua', palatino;">Accordingly, “<span class="math inline">\(\text{Step}(p,n,s,t,m,r,s',t',m',r')\)</span>” can be defined in <span class="math inline">\(L\)</span> as follows: <span class="math display">\[\begin{array}{l} \text{Step}(p,n,s,t,m,r,s',t',m',r') \leftrightarrow_{df} \\ \quad \quad \forall i ((1 \leq i \,\&\, \neg(i=r)) \supset \exists z (\text{ReadSymb}(z,i,t,m) \,\&\, \text{ReadSymb}(z,i,t',m'))) \ \& \\ \quad \quad \exists y \, \exists y' \, (\text{FirstLine}(p,n,s,y,y',(r\!-\!r')\!-\!1,s') \ \& \ \text{ReadSymb}(y,r,t,m) \ \& \\ \hspace{90mm} \text{ReadSymb}(y',r,t',m')) \end{array}\]</span> With “<span class="math inline">\(\text{Step}(p,n,s,t,m,r,s',t',m',r')\)</span>” in place, it is easy to define a formula “<span class="math inline">\(\text{Step}(a,b)\)</span>” which is true if and only if: <span class="math inline">\(a\)</span> codes a sequence <span class="math inline">\(\langle p,n,s,t,m,r\rangle\)</span>, <span class="math inline">\(b\)</span> codes a sequence <span class="math inline">\(\langle p,n,s',t',m',r'\rangle\)</span> and <span class="math inline">\(\text{Step}(p,n,s,t,m,r,s',t',m',r')\)</span>: <span class="math display">\[\begin{array}{ccl} \text{Step}(a,b) &\leftrightarrow_{df} &\exists p \exists n \exists s \exists t \exists m \exists r \exists s' \exists t' \exists m' \exists r' (\text{Seq}(a,5,p,1) \ \& \ \text{Seq}(a,5,n,2) \ \& \ \text{Seq}(a,5,s,3) \ \& \\ & &\hspace{52mm} \text{Seq}(a,5,t,4) \ \& \ \text{Seq}(a,5,m,5) \ \& \ \text{Seq}(a,5,r,6) \ \& \\ & &\hspace{52mm} \text{Seq}(b,5,p,1) \ \& \ \text{Seq}(b,5,n,2) \ \& \ \text{Seq}(b,3,s',6) \ \& \\ & &\hspace{52mm} \text{Seq}(b,5,t',4) \ \& \ \text{Seq}(b,5,m',5) \ \& \ \text{Seq}(b,5,r',6) \ \& \\ & &\hspace{52mm} \text{Step}(p,n,s,t,m,r,s',t',m',r')) \end{array}\]</span></span></p>
<p></p>
</div>
</div>
<div class="vert vert-5" data-id="block-v1:MITx+24.118x+2T2020+type@video+block@2d19140e09b94ccba4674645a4589825">
<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@2d19140e09b94ccba4674645a4589825" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="4dff59f45adc11ef94f5022c6f26e6af" 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 Jump Sentence</h3>
<div
id="video_2d19140e09b94ccba4674645a4589825"
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@2d19140e09b94ccba4674645a4589825/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@2d19140e09b94ccba4674645a4589825/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@2d19140e09b94ccba4674645a4589825/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@2d19140e09b94ccba4674645a4589825/handler/transcript/translation/__lang__", "transcriptLanguages": {"en": "English"}, "streams": "1.00:8wXmwq9afJI", "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="2d19140e09b94ccba4674645a4589825"></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_2d19140e09b94ccba4674645a4589825">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_2d19140e09b94ccba4674645a4589825">
<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@2d19140e09b94ccba4674645a4589825/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@2d19140e09b94ccba4674645a4589825/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
<div class="vert vert-6" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@9b8c864b3e2e4d34860539843d625cec">
<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@9b8c864b3e2e4d34860539843d625cec" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="4dff59f45adc11ef94f5022c6f26e6af" data-graded="False">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<h4><span style="font-family: 'book antiqua', palatino;">Run-Sequences</span></h4>
<p><span style="font-family: 'book antiqua', palatino;">We are now in a position to define a formula “<span class="math inline">\(\mbox{RunSequence}(s,j,k,i)\)</span>”, which is true just in case <span class="math inline">\(s\)</span> encodes a sequence of <span class="math inline">\(j\)</span> steps of a Turing Machine’s operation. In the first member of the sequence, the <span class="math inline">\(k\)</span>th Turing Machine is initialized on input <span class="math inline">\(i\)</span>; in the last member of the sequence the machine halts; and one can get from any member of the sequence to its successor by performing a step of the <span class="math inline">\(k\)</span>th Turing Machine’s operation. Here is one way of defining “<span class="math inline">\(\mbox{RunSequence}(s,j,k,i)\)</span>”: <span class="math display">\[\begin{array}{l} \mbox{RunSequence}(s,m,k,i) \leftrightarrow_{df} \\ \hspace{10mm} \exists a \exists z (\text{Seq}(s,m,a,1) \ \& \ \text{Seq}(s,m,z,m) \ \& \ \text{Initial}(k,i,a) \ \& \ \text{Halted}(z)) \ \& \\ \hspace{10mm} \forall i \forall a \forall b ((1 \leq i \,\&\, i < m \,\&\, \text{Seq}(s,m,a,i) \,\&\,\text{Seq}(s,m,b,i+1)) \supset \text{Step}(a,b)) \end{array}\]</span></span></p>
<p></p>
</div>
</div>
<div class="vert vert-7" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@0bc7b3da1e1b4fadbecd444abc07e97d">
<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@0bc7b3da1e1b4fadbecd444abc07e97d" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="4dff59f45adc11ef94f5022c6f26e6af" data-graded="False">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<h4><span style="font-family: 'book antiqua', palatino;">The Halting Function</span></h4>
<p><span style="font-family: 'book antiqua', palatino;">At long last we are in a position to use a formula of <span class="math inline">\(L\)</span> to describe the Halting Function, <span class="math inline">\(H(k)\)</span>, which we introduced in Chapter 9. Recall that <span class="math inline">\(H(k) = 1\)</span> if the <span class="math inline">\(k\)</span>th Turing Machine halts on input <span class="math inline">\(k\)</span>, and <span class="math inline">\(H(k) = 0\)</span>, otherwise.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">We will express the thought that <span class="math inline">\(H(k) =1\)</span> by defining formula “<span class="math inline">\(\text{Halt}(k)\)</span>”, which is true if and only if the <span class="math inline">\(k\)</span>th Turing Machine halts on input <span class="math inline">\(k\)</span>: <span class="math display">\[\begin{array}{ccl} \text{Halt}(k) &\leftrightarrow_{df} & \exists s \exists j (\mbox{RunSequence}(s,j,k,k)) \end{array}\]</span> We have worked long and hard, and introduced many syntactic abbreviations along the way. But it is worth keeping mind that, at the end of the day, “<span class="math inline">\(\text{Halt}(k)\)</span>” is shorthand for a formula of <span class="math inline">\(L\)</span>, which can be built using only variables, and the symbols “<span class="math inline">\((\)</span>”, “<span class="math inline">\()\)</span>”, “<span class="math inline">\(0\)</span>”, “<span class="math inline">\(1\)</span>”, “<span class="math inline">\(+\)</span>”, “<span class="math inline">\(\times\)</span>”, “<span class="math inline">\(\wedge\)</span>”, “<span class="math inline">\(\neg\)</span>”, “<span class="math inline">\(\&\)</span>”, and “<span class="math inline">\(\forall\)</span>”.</span></p>
<p></p>
</div>
</div>
<div class="vert vert-8" data-id="block-v1:MITx+24.118x+2T2020+type@video+block@d89ecdfce74f41f2b6e74aa89a8819ba">
<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@d89ecdfce74f41f2b6e74aa89a8819ba" data-course-id="course-v1:MITx+24.118x+2T2020" data-request-token="4dff59f45adc11ef94f5022c6f26e6af" data-graded="False">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video Review: Halting in L</h3>
<div
id="video_d89ecdfce74f41f2b6e74aa89a8819ba"
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@d89ecdfce74f41f2b6e74aa89a8819ba/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@d89ecdfce74f41f2b6e74aa89a8819ba/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@d89ecdfce74f41f2b6e74aa89a8819ba/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@d89ecdfce74f41f2b6e74aa89a8819ba/handler/transcript/translation/__lang__", "transcriptLanguages": {"en": "English"}, "streams": "1.00:HtHviveUkio", "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="d89ecdfce74f41f2b6e74aa89a8819ba"></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_d89ecdfce74f41f2b6e74aa89a8819ba">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_d89ecdfce74f41f2b6e74aa89a8819ba">
<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@d89ecdfce74f41f2b6e74aa89a8819ba/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@d89ecdfce74f41f2b6e74aa89a8819ba/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
© All Rights Reserved