Permalink
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
250 lines (249 sloc) 15.7 KB
<h2><img class="pluginslug" src="/plugin_helper.php?plugin=external&amp;name=x&amp;code=%3Cscript+src%3D%22%2Ff%2Fquizcss.js%22%3E%3C%2Fscript%3E%0A%3Cscript+src%3D%22%2Ff%2Fjquery.js%22%3E%3C%2Fscript%3E%0A%3Cscript+src%3D%22%2Ff%2Fquiz.js%22%3E%3C%2Fscript%3E&amp;nofilter=1&amp;sig=kW2L0AcF2wpg3OzKFPaU" alt="" />This quiz tests&nbsp;your understanding of computability thery (primitive recursion, Turing machines, partial recursive functions, recursive and recursively enumerable sets)</h2>
<p>&nbsp;</p>
<p style="text-align: right;"><span style="font-size: 75%;"><span id="answerkey">(Key: <span class="correct">correct</span>, <span class="incorrect">incorrect</span>, <span class="partially">partially correct</span>.)</span></span></p>
<p>&nbsp;</p>
<p>This is a draft. I am making edits on the wiki to be able to preview the quiz as I make it.</p>
<ol id="questions">
<li>Which of the following has a different meaning than the rest?</li>
<ol>
<li>Recursively enumerable set</li>
<li>Semirecursive set</li>
<li>Effectively enumerable set</li>
<ul>
<li>PARTIALLY. This is equivalent to most of the others. However, note that "effectively" is an informal notion so we are implicitly invoking the Church–Turing thesis. This means that philosophically, it is somewhat different than the more formal alternatives, but at the end of the day, it is essentially referring to the same thing.</li>
</ul>
<li>Computably enumerable set</li>
<li>Turing-recognizable set</li>
<li>Partially recursive set</li>
<ul>
<li>CORRECT. This option is unlike the others in a trivial sense: it's not even a term that is defined! This question is included here at the beginning because later in the quiz, we will be free to alternate between these equivalent terms.</li>
</ul>
</ol>
<li>Which of the following has a different meaning than the rest?</li>
<ol>
<li>Recursive set</li>
<li>Computable set</li>
<li>Decidable set</li>
<li>Effectively computable set</li>
<ul>
<li>PARTIALLY. This is equivalent to most of the others. However, note that "effectively" is an informal notion so we are implicitly invoking the Church–Turing thesis. This means that philosophically, it is somewhat different than the more formal alternatives, but at the end of the day, it is essentially referring to the same thing.</li>
</ul>
<li>Computably enumerable set</li>
<ul>
<li>CORRECT.</li>
</ul>
</ol>
<li>Which of the following has a different meaning than the rest?</li>
<ol>
<li>Partial recursive function</li>
<li>Partial μ-recursive function</li>
<li>Computable total or partial function</li>
<li>Recursive total or partial function</li>
<li>General recursive total or partial function</li>
<li>Turing-computable total or partial function</li>
<li>Effectively calculable total or partial function</li>
<ul>
<li>PARTIALLY. This is equivalent to most of the others. However, note that "effectively" is an informal notion so we are implicitly invoking the Church–Turing thesis. This means that philosophically, it is somewhat different than the more formal alternatives, but at the end of the day, it is essentially referring to the same thing.</li>
</ul>
<li>Effectively computable total or partial function</li>
<ul>
<li>PARTIALLY. This is equivalent to most of the others. However, note that "effectively" is an informal notion so we are implicitly invoking the Church–Turing thesis. This means that philosophically, it is somewhat different than the more formal alternatives, but at the end of the day, it is essentially referring to the same thing.</li>
</ul>
<li>Primitive recursive function</li>
<ul>
<li>CORRECT. This is a weaker notion than the rest, i.e., all primitive recursive functions are partial recursive, but there exist partial recursive functions that are not primitive recursive.</li>
</ul>
</ol>
<li>Let <em>S</em> be a one-place semirecursive relation on <b>N</b>, and let us attempt to define a partial function <em>f</em>:&nbsp;<b>N</b>&nbsp;&nbsp;<b>N</b> as follows: if <em>S</em>(<em>n</em>) then <em>f</em>(<em>n</em>)&nbsp;=&nbsp;1, and if not <em>S</em>(<em>n</em>) then <em>f</em>(<em>n</em>)&nbsp;=&nbsp;0. What is the strongest statement we can make about <em>f</em>?</li>
<ol>
<li><em>f</em> is well-defined</li>
<ul>
<li>PARTIALLY. Indeed <em>f</em> is well-defined, but we can say something stronger.</li>
</ul>
<li><em>f</em> is total</li>
<ul>
<li>CORRECT. <em>f</em> is total because exactly one of <em>S</em>(<em>n</em>) or ¬<em>S</em>(<em>n</em>) holds for each <em>n</em>&nbsp;&nbsp;<b>N</b> (law of excluded middle).</li>
</ul>
<li><em>f</em> is recursive and total (<em>f</em> is a computable total function)</li>
<ul>
<li>INCORRECT. <em>S</em> is only semirecursive, so both <em>S</em> and ¬<em>S</em> may end up in an infinite loop.</li>
</ul>
<li>None of the other options; <i>f</i> is ill-defined.</li>
</ol>
<li>Let <em>S</em> be a subset of the natural numbers. Which of the following is <em>not</em> equivalent to saying that <em>S</em> is recursively enumerable?</li>
<ol>
<li><em>S</em> is the domain of a computable partial function</li>
<li><em>S</em> can be enumerated in a computable manner as <em>a</em>₀, <em>a</em>₁, <em>a</em>₂, … in increasing order</li>
<ul>
<li>CORRECT. This is equivalent to saying <em>S</em> is recursive, and there exist recursively enumerable sets that are not recursive.</li>
</ul>
<li><em>S</em> is the range of a computable partial function</li>
<li>There exists a two-place recursive relation <em>R</em> on <b>N</b> such that <em>x</em>&nbsp;&nbsp;<em>S</em> iff ∃<em>t</em>&nbsp;<em>R</em>(<em>x</em>,&nbsp;<em>t</em>)</li>
<li><em>S</em> is empty or the range of a primitive recursive function</li>
</ol>
<li>Let <em>f</em>:&nbsp;<b>N</b>&nbsp;&nbsp;<b>N</b> be a partial function. Which of the following is <em>not</em> equivalent to saying that <em>f</em> is computable?</li>
<ol>
<li><em>f</em> is computable by a Turing machine</li>
<li><em>f</em> is definable from the basic functions (zero, successor, identity) using the processes of composition, primitive recursion, and minimization</li>
<li><em>f</em> is computable by a register machine (abacus machine)</li>
<li><em>f</em> is computable by a program that uses basic operations (clearing, increment, copy) and a bounded loop</li>
<ul>
<li>CORRECT. This is equivalent to saying <em>f</em> is primitive recursive, and there exist recursive functions that are not primitive recursive.</li>
</ul>
</ol>
<li>What is the strongest statement we can make about the set of all real numbers?</li>
<ol>
<li>It is enumerable</li>
<li>It is recursively enumerable</li>
<li>It is recursive</li>
<li>It is primitive recursive</li>
<li>We cannot say any of the other options</li>
<ul>
<li>CORRECT. The weakest statement is enumerability, but <b>R</b> is uncountable so it cannot be enumerated.</li>
</ul>
</ol>
<li>What is the strongest statement we can make about the set of even natural numbers?</li>
<ol>
<li>It is enumerable</li>
<li>It is recursively enumerable</li>
<li>It is recursive</li>
<li>It is primitive recursive</li>
<ul>
<li>CORRECT.</li>
</ul>
<li>We cannot say any of the other options</li>
</ol>
<li>What is the strongest statement we can make about the set of all natural numbers?</li>
<ol>
<li>It is enumerable</li>
<li>It is recursively enumerable</li>
<li>It is recursive</li>
<li>It is primitive recursive</li>
<ul>
<li>CORRECT.</li>
</ul>
<li>We cannot say any of the other options</li>
</ol>
<li>What is the strongest statement we can make about the set of all rational numbers?</li>
<ol>
<li>It is enumerable</li>
<li>It is recursively enumerable</li>
<li>It is recursive</li>
<li>It is primitive recursive</li>
<ul>
<li>CORRECT.</li>
</ul>
<li>We cannot say any of the other options</li>
</ol>
<li>What is the strongest statement we can make about the set of all pairs (<i>m</i>,&nbsp;<i>n</i>) such that the <i>m</i>th Turing machine when started with input <i>n</i> halts?</li>
<ol>
<li>It is enumerable</li>
<ul>
<li>CORRECT.</li>
</ul>
<li>It is recursively enumerable</li>
<li>It is recursive</li>
<li>It is primitive recursive</li>
<li>We cannot say any of the other options</li>
</ol>
<li>Can a characteristic function for a set of natural numbers be non-total?</li>
<ol>
<li>No; for every input natural number, a characteristic function must output 0 or 1 depending on whether the number is in the set or not. This means the characteristic function is always total.</li>
<ul>
<li>CORRECT. However, note that there are also positive semicharacteristic functions, which need not be total.</li>
</ul>
<li>Yes; for instance, the characteristic function of a semirecursive set is only defined for some inputs.</li>
<ul>
<li>The characteristic function of a semirecursive set is actually total. However, that characteristic function need not be <em>computable</em>.</li>
</ul>
</ol>
<li>Which of the following operations are the semirecursive relations <em>not</em> closed under?</li>
<ol>
<li>Conjunction (logical AND)</li>
<li>Disjunction (logical OR)</li>
<li>Negation (logical NOT)</li>
<ul>
<li>CORRECT.</li>
</ul>
<li>Bounded universal quantification</li>
<li>Bounded existential quantification</li>
<li>Existential quantification (not necessarily bounded)</li>
<ul>
<li>INCORRECT. A semirecursive relation already can be written in the form ∃t&nbsp;<i>R</i>(<i>x</i>,&nbsp;<i>t</i>) for some recursive relation <i>R</i>. Intuitively, adding on more existential quantifiers at the beginning doesn't change the "kind" of relation. More carefully, if we have <i>S</i>(<i>x</i>,&nbsp;<i>y</i>) iff ∃<i>t</i>&nbsp;<i>R</i>(<i>x</i>,&nbsp;<i>y</i>,&nbsp;<i>t</i>) for some recursive relation <i>R</i>, then we can write the relation ∃<i>y</i>&nbsp;<i>S</i>(<i>x</i>,&nbps;<i>y</i>) as ∃<i>M</i>&nbsp;∃<i>y</i>&lt;<i>M</i>&nbsp;∃<i>t</i>&lt;<i>M</i>&nbsp;<i>R</i>(<i>x</i>,&nbsp;<i>y</i>,&nbsp;<i>t</i>), where ∃<i>y</i>&lt;<i>M</i>&nbsp;∃<i>t</i>&lt;<i>M</i>&nbsp;<i>R</i>(<i>x</i>,&nbsp;<i>y</i>,&nbsp;<i>t</i>) is recursive (as it only uses bounded quantification). In other words, we can combine the two unbounded existential quantifiers into a single unbounded "upper bound" and use bounded existential quantifiers for the rest.</li>
</ul>
</ol>
<li>What information does a single instruction in a Turing machine use? (Alternatively, what are the inputs to the transition function of a Turing machine?)</li>
<ol>
<li>A symbol</li>
<li>A symbol and a state</li>
<li>A symbol and an action</li>
<ul>
<li>CORRECT.</li>
</ul>
<li>A symbol, a state, and an action</li>
<li>A symbol, two states, and an action</li>
<ul>
<li>INCORRECT. This is what a full instruction looks like, but only the symbol and one of the states are used; the other state and the action are the <em>outputs</em> of the transition function.</li>
</ul>
</ol>
<li>Which of the following is an incorrect explanation of why there is a countable number of Turing-computable functions?</li>
<ol>
<li>We can encode each Turing machine by a list of quadruples (in-state, scanned symbol, output action, out-state)</li>
<ul>
<li>INCORRECT. This is the most direct way to show that there are a countable number of Turing-computable functions.</li>
</ul>
<li>Turing machines are basically computer programs, whose source code can be written as finite strings of a finite alphabet; therefore, there are a countable number of them</li>
<ul>
<li>PARTIALLY. This explanation works, but it sort of appeals to the Church–Turing thesis.</li>
</ul>
<li>Turing-computable functions are equivalent to partial recursive functions, and there are a countable number of partial recursive functions.</li>
<ul>
<li>PARTIALLY. While this is not wrong, the equivalence of Turing computability and recursiveness is sort of a more advanced fact (also, does the proof the equivalence use countability anywhere?).</li>
</ul>
<li>A Turing machine comes with an infinitely long tape which is countable. At any stage during the computation, only finitely many squares on the tape have a symbol written on them. Therefore, there are a countable number of Turing machines.</li>
<ul>
<li>CORRECT. This explains why the <em>configuration</em> of a stage of computation is finite, but doesn't explain why there are countably many Turing machines.</li>
</ul>
</ol>
<li>Let <i>f</i>: <b>N</b> → <b>N</b> be a computable partial function. What can we say about the graph relation <i>G</i> of <i>f</i>, defined by <i>G</i>(<i>x</i>, <i>y</i>) iff <i>f</i>(<i>x</i>) = <i>y</i>?</li>
<ol>
<li><i>G</i> is partial recursive</li>
<li><i>G</i> is recursive</li>
<li><i>G</i> is semirecursive</li>
<ul>
<li>CORRECT.</li>
</ul>
<li>Nothing; we cannot in general conclude anything about <i>G</i></li>
</ol>
<li>Let <i>f</i>: <b>N</b> → <b>N</b> be a partial function. Suppose the graph relation <i>G</i> of <i>f</i>, defined by <i>G</i>(<i>x</i>, <i>y</i>) iff <i>f</i>(<i>x</i>) = <i>y</i>, is a semirecursive relation. What can we say about <i>f</i>?</li>
<ol>
<li><i>f</i> is primitive recursive</li>
<li><i>f</i> is partial recursive</li>
<ul>
<li>CORRECT.</li>
</ul>
<li><i>f</i> is recursive and total</li>
<li><i>f</i> is semirecursive</li>
<ul>
<li>INCORRECT. It does not make sense to ask whether a partial function is semirecursive (we can only ask this for relations and sets).</li>
</ul>
<li>Nothing; we cannot in general conclude anything about <i>G</i></li>
</ol>
<li>If <i>f</i>: <b>N</b><sup><i>k</i></sup> → <b>N</b> is a <i>k</i>-place partial recursive function, then the result of applying the minimization operator (also called the μ operator) to <i>f</i> is</li>
<ol>
<li>A (<i>k</i>&thinsp;&minus;&thinsp;1)-place partial recursive function</li>
<ul>
<li>CORRECT.</li>
</ul>
<li>A <i>k</i>-place partial recursive function</li>
<li>A (<i>k</i>&thinsp;+&thinsp;1)-place partial recursive function</li>
<li>A subset of <b>N</b><sup><i>k</i>&thinsp;&minus;&thinsp;1</sup></li>
<li>A subset of <b>N</b><sup><i>k</i></sup></li>
<li>A subset of <b>N</b><sup><i>k</i>&thinsp;+&thinsp;1</sup></li>
<li>A natural number</li>
</ol>
</ol>
<p>&nbsp;</p>
<h2><span style="font-weight: bold;">Score: <span id="score">&nbsp;</span></span></h2>
<p id="expandlink" style="text-align: right; font-size: 75%;">.</p>
<p>&nbsp;</p>