<div class="xblock xblock-public_view xblock-public_view-vertical" data-init="VerticalStudentView" data-has-score="False" data-runtime-version="1" data-graded="True" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@e1bcab605d794f7199db3c0b8afac832" data-runtime-class="LmsRuntime" data-block-type="vertical" data-request-token="2940f144028611efb5ee02329aca76dd" data-course-id="course-v1:MITx+24.118x+2T2020">
<h2 class="hd hd-2 unit-title">Homework</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@ef1b13199bb94d519e12249acc1454d5">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-init="XBlockToXModuleShim" data-has-score="False" data-runtime-version="1" data-graded="True" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@ef1b13199bb94d519e12249acc1454d5" data-runtime-class="LmsRuntime" data-block-type="html" data-request-token="2940f144028611efb5ee02329aca76dd" data-course-id="course-v1:MITx+24.118x+2T2020">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p>The exercises below will count towards your grade. <strong>You have only one chance to answer these questions. </strong>Take your time, and think carefully before answering.</p>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+24.118x+2T2020+type@problem+block@95568b970c10433bb1b877609b0c1654">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-init="XBlockToXModuleShim" data-has-score="True" data-runtime-version="1" data-graded="True" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@95568b970c10433bb1b877609b0c1654" data-runtime-class="LmsRuntime" data-block-type="problem" data-request-token="2940f144028611efb5ee02329aca76dd" data-course-id="course-v1:MITx+24.118x+2T2020">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_95568b970c10433bb1b877609b0c1654" class="problems-wrapper" role="group"
aria-labelledby="95568b970c10433bb1b877609b0c1654-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@95568b970c10433bb1b877609b0c1654" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@95568b970c10433bb1b877609b0c1654/handler/xmodule_handler"
data-problem-score="0.0"
data-problem-total-possible="20.0"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="95568b970c10433bb1b877609b0c1654-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@95568b970c10433bb1b877609b0c1654-problem-progress" tabindex="-1">
Problem 1
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@95568b970c10433bb1b877609b0c1654-problem-progress"></div>
<div class="problem">
<div>
<p>Answer the following questions using the coding system described in ''Numberint Turing Machines'', <a href="/courses/course-v1:MITx+24.118x+2T2020/jump_to_id/6ae42c64326d471cb0899557527829c2">above</a>.</p>
<p>Which natural number codes the Turing Machine with program \( 0 \: \_ \: \_ \: l \: 0 \)?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="formulaequationinput_95568b970c10433bb1b877609b0c1654_2_1" class="inputtype formulaequationinput">
<div class="unanswered">
<input type="text" name="input_95568b970c10433bb1b877609b0c1654_2_1" id="input_95568b970c10433bb1b877609b0c1654_2_1" data-input-id="95568b970c10433bb1b877609b0c1654_2_1" value="" aria-describedby="status_95568b970c10433bb1b877609b0c1654_2_1" size="20"/>
<span class="trailing_text" id="trailing_text_95568b970c10433bb1b877609b0c1654_2_1"/>
<span class="status unanswered" id="status_95568b970c10433bb1b877609b0c1654_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_95568b970c10433bb1b877609b0c1654_2_1" class="answer"/>
<div id="input_95568b970c10433bb1b877609b0c1654_2_1_preview" class="equation">
\(\)
<img src="/static/images/spinner.bc34f953403f.gif" class="loading" alt="Loading"/>
</div>
</div>
<div class="script_placeholder" data-src="/static/js/capa/src/formula_equation_preview.b1967ab28c31.js"/>
</div></div>
<div class="solution-span">
<span id="solution_95568b970c10433bb1b877609b0c1654_solution_1"/>
</div><p><br/>What does this Turing Machine do, on an empty input?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div class="choicegroup capa_inputtype" id="inputtype_95568b970c10433bb1b877609b0c1654_3_1">
<fieldset aria-describedby="status_95568b970c10433bb1b877609b0c1654_3_1">
<div class="field">
<input type="radio" name="input_95568b970c10433bb1b877609b0c1654_3_1" id="input_95568b970c10433bb1b877609b0c1654_3_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="95568b970c10433bb1b877609b0c1654_3_1-choice_0-label" for="input_95568b970c10433bb1b877609b0c1654_3_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_95568b970c10433bb1b877609b0c1654_3_1"> Goes rightward on the tape forever, leaving the tape unchanged.
</label>
</div>
<div class="field">
<input type="radio" name="input_95568b970c10433bb1b877609b0c1654_3_1" id="input_95568b970c10433bb1b877609b0c1654_3_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="95568b970c10433bb1b877609b0c1654_3_1-choice_1-label" for="input_95568b970c10433bb1b877609b0c1654_3_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_95568b970c10433bb1b877609b0c1654_3_1"> Goes rightward on the tape forever, changing whatever is on the tape to a string of ones.
</label>
</div>
<div class="field">
<input type="radio" name="input_95568b970c10433bb1b877609b0c1654_3_1" id="input_95568b970c10433bb1b877609b0c1654_3_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="95568b970c10433bb1b877609b0c1654_3_1-choice_2-label" for="input_95568b970c10433bb1b877609b0c1654_3_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_95568b970c10433bb1b877609b0c1654_3_1"> Goes leftward on the tape forever, leaving the tape unchanged.
</label>
</div>
<div class="field">
<input type="radio" name="input_95568b970c10433bb1b877609b0c1654_3_1" id="input_95568b970c10433bb1b877609b0c1654_3_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="95568b970c10433bb1b877609b0c1654_3_1-choice_3-label" for="input_95568b970c10433bb1b877609b0c1654_3_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_95568b970c10433bb1b877609b0c1654_3_1"> Goes leftward on the tape forever, changing whatever is on the tape to a string of ones.
</label>
</div>
<span id="answer_95568b970c10433bb1b877609b0c1654_3_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_95568b970c10433bb1b877609b0c1654_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_95568b970c10433bb1b877609b0c1654_solution_2"/>
</div><p>Which natural number codes the Turing Machine with program \( 0 \: 1 \: \_ \: r \: 0 \)?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 3" role="group"><div id="formulaequationinput_95568b970c10433bb1b877609b0c1654_4_1" class="inputtype formulaequationinput">
<div class="unanswered">
<input type="text" name="input_95568b970c10433bb1b877609b0c1654_4_1" id="input_95568b970c10433bb1b877609b0c1654_4_1" data-input-id="95568b970c10433bb1b877609b0c1654_4_1" value="" aria-describedby="status_95568b970c10433bb1b877609b0c1654_4_1" size="20"/>
<span class="trailing_text" id="trailing_text_95568b970c10433bb1b877609b0c1654_4_1"/>
<span class="status unanswered" id="status_95568b970c10433bb1b877609b0c1654_4_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_95568b970c10433bb1b877609b0c1654_4_1" class="answer"/>
<div id="input_95568b970c10433bb1b877609b0c1654_4_1_preview" class="equation">
\(\)
<img src="/static/images/spinner.bc34f953403f.gif" class="loading" alt="Loading"/>
</div>
</div>
<div class="script_placeholder" data-src="/static/js/capa/src/formula_equation_preview.b1967ab28c31.js"/>
</div></div>
<div class="solution-span">
<span id="solution_95568b970c10433bb1b877609b0c1654_solution_3"/>
</div><p><br/>What does this Turing Machine do, on an empty input?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 4" role="group"><div class="choicegroup capa_inputtype" id="inputtype_95568b970c10433bb1b877609b0c1654_5_1">
<fieldset aria-describedby="status_95568b970c10433bb1b877609b0c1654_5_1">
<div class="field">
<input type="radio" name="input_95568b970c10433bb1b877609b0c1654_5_1" id="input_95568b970c10433bb1b877609b0c1654_5_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="95568b970c10433bb1b877609b0c1654_5_1-choice_0-label" for="input_95568b970c10433bb1b877609b0c1654_5_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_95568b970c10433bb1b877609b0c1654_5_1"> It will go rightward on the tape forever.
</label>
</div>
<div class="field">
<input type="radio" name="input_95568b970c10433bb1b877609b0c1654_5_1" id="input_95568b970c10433bb1b877609b0c1654_5_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="95568b970c10433bb1b877609b0c1654_5_1-choice_1-label" for="input_95568b970c10433bb1b877609b0c1654_5_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_95568b970c10433bb1b877609b0c1654_5_1"> It will go leftward on the tape forever.
</label>
</div>
<div class="field">
<input type="radio" name="input_95568b970c10433bb1b877609b0c1654_5_1" id="input_95568b970c10433bb1b877609b0c1654_5_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="95568b970c10433bb1b877609b0c1654_5_1-choice_2-label" for="input_95568b970c10433bb1b877609b0c1654_5_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_95568b970c10433bb1b877609b0c1654_5_1"> It will halt immediately.
</label>
</div>
<span id="answer_95568b970c10433bb1b877609b0c1654_5_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_95568b970c10433bb1b877609b0c1654_5_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_95568b970c10433bb1b877609b0c1654_solution_4"/>
</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_95568b970c10433bb1b877609b0c1654" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_95568b970c10433bb1b877609b0c1654">
<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="95568b970c10433bb1b877609b0c1654-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="95568b970c10433bb1b877609b0c1654-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="95568b970c10433bb1b877609b0c1654-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="True">
<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-2" data-id="block-v1:MITx+24.118x+2T2020+type@problem+block@b6badadf48c34684b101d48c7d3be073">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-init="XBlockToXModuleShim" data-has-score="True" data-runtime-version="1" data-graded="True" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@b6badadf48c34684b101d48c7d3be073" data-runtime-class="LmsRuntime" data-block-type="problem" data-request-token="2940f144028611efb5ee02329aca76dd" data-course-id="course-v1:MITx+24.118x+2T2020">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_b6badadf48c34684b101d48c7d3be073" class="problems-wrapper" role="group"
aria-labelledby="b6badadf48c34684b101d48c7d3be073-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@b6badadf48c34684b101d48c7d3be073" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@b6badadf48c34684b101d48c7d3be073/handler/xmodule_handler"
data-problem-score="0.0"
data-problem-total-possible="10.0"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="b6badadf48c34684b101d48c7d3be073-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@b6badadf48c34684b101d48c7d3be073-problem-progress" tabindex="-1">
Problem 2
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@b6badadf48c34684b101d48c7d3be073-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><p>Here is a Turing Machine:</p>
<p style="padding-left:30px;"> \[ 0 \: \_ \: 1 \: R \: 1 \] </p>
<p style="padding-left:30px;"> \[ 1 \: \_ \: 1 \: L \: 2 \] </p>
<p style="padding-left:30px;"> \[ 2 \: 1 \: \_ \: R \: 3 \] </p>
<p style="padding-left:30px;"> \[ 3 \: 1 \: \_ \: L \: 0 \] </p>
<p>What does this Turing Machine do, when run on an empty input?</p>
<div class="choicegroup capa_inputtype" id="inputtype_b6badadf48c34684b101d48c7d3be073_2_1">
<fieldset aria-describedby="status_b6badadf48c34684b101d48c7d3be073_2_1">
<div class="field">
<input type="radio" name="input_b6badadf48c34684b101d48c7d3be073_2_1" id="input_b6badadf48c34684b101d48c7d3be073_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="b6badadf48c34684b101d48c7d3be073_2_1-choice_0-label" for="input_b6badadf48c34684b101d48c7d3be073_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_b6badadf48c34684b101d48c7d3be073_2_1"> It goes rightward forever, not changing anything.
</label>
</div>
<div class="field">
<input type="radio" name="input_b6badadf48c34684b101d48c7d3be073_2_1" id="input_b6badadf48c34684b101d48c7d3be073_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="b6badadf48c34684b101d48c7d3be073_2_1-choice_1-label" for="input_b6badadf48c34684b101d48c7d3be073_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_b6badadf48c34684b101d48c7d3be073_2_1"> It goes back and forth forever, changing blanks to '\(1\)'s and '\(1\)'s to blanks.
</label>
</div>
<div class="field">
<input type="radio" name="input_b6badadf48c34684b101d48c7d3be073_2_1" id="input_b6badadf48c34684b101d48c7d3be073_2_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="b6badadf48c34684b101d48c7d3be073_2_1-choice_2-label" for="input_b6badadf48c34684b101d48c7d3be073_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_b6badadf48c34684b101d48c7d3be073_2_1"> It goes right and then left, back and forth forever, not changing anything.
</label>
</div>
<span id="answer_b6badadf48c34684b101d48c7d3be073_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_b6badadf48c34684b101d48c7d3be073_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_b6badadf48c34684b101d48c7d3be073_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_b6badadf48c34684b101d48c7d3be073" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_b6badadf48c34684b101d48c7d3be073">
<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="b6badadf48c34684b101d48c7d3be073-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="b6badadf48c34684b101d48c7d3be073-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="b6badadf48c34684b101d48c7d3be073-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="True">
<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@798c34e297ea4272a061922af29366b6">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-init="XBlockToXModuleShim" data-has-score="True" data-runtime-version="1" data-graded="True" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@798c34e297ea4272a061922af29366b6" data-runtime-class="LmsRuntime" data-block-type="problem" data-request-token="2940f144028611efb5ee02329aca76dd" data-course-id="course-v1:MITx+24.118x+2T2020">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_798c34e297ea4272a061922af29366b6" class="problems-wrapper" role="group"
aria-labelledby="798c34e297ea4272a061922af29366b6-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@798c34e297ea4272a061922af29366b6" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@798c34e297ea4272a061922af29366b6/handler/xmodule_handler"
data-problem-score="0.0"
data-problem-total-possible="20.0"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="798c34e297ea4272a061922af29366b6-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@798c34e297ea4272a061922af29366b6-problem-progress" tabindex="-1">
Problem 3
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@798c34e297ea4272a061922af29366b6-problem-progress"></div>
<div class="problem">
<div>
<p>For each Turing Machine, say whether it halts on an empty input:</p>
<p style="padding-left:30px;"> \[ 0 \: \_ \: \_ \: R \: 0 \] </p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_798c34e297ea4272a061922af29366b6_2_1">
<fieldset aria-describedby="status_798c34e297ea4272a061922af29366b6_2_1">
<div class="field">
<input type="radio" name="input_798c34e297ea4272a061922af29366b6_2_1" id="input_798c34e297ea4272a061922af29366b6_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="798c34e297ea4272a061922af29366b6_2_1-choice_0-label" for="input_798c34e297ea4272a061922af29366b6_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_798c34e297ea4272a061922af29366b6_2_1"> Doesn't halt
</label>
</div>
<div class="field">
<input type="radio" name="input_798c34e297ea4272a061922af29366b6_2_1" id="input_798c34e297ea4272a061922af29366b6_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="798c34e297ea4272a061922af29366b6_2_1-choice_1-label" for="input_798c34e297ea4272a061922af29366b6_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_798c34e297ea4272a061922af29366b6_2_1"> Halts
</label>
</div>
<span id="answer_798c34e297ea4272a061922af29366b6_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_798c34e297ea4272a061922af29366b6_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_798c34e297ea4272a061922af29366b6_solution_1"/>
</div><p style="padding-left:30px;"> \[ 0 \: \_ \: 1 \: R \: 1 \] </p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div class="choicegroup capa_inputtype" id="inputtype_798c34e297ea4272a061922af29366b6_3_1">
<fieldset aria-describedby="status_798c34e297ea4272a061922af29366b6_3_1">
<div class="field">
<input type="radio" name="input_798c34e297ea4272a061922af29366b6_3_1" id="input_798c34e297ea4272a061922af29366b6_3_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="798c34e297ea4272a061922af29366b6_3_1-choice_0-label" for="input_798c34e297ea4272a061922af29366b6_3_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_798c34e297ea4272a061922af29366b6_3_1"> Doesn't halt
</label>
</div>
<div class="field">
<input type="radio" name="input_798c34e297ea4272a061922af29366b6_3_1" id="input_798c34e297ea4272a061922af29366b6_3_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="798c34e297ea4272a061922af29366b6_3_1-choice_1-label" for="input_798c34e297ea4272a061922af29366b6_3_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_798c34e297ea4272a061922af29366b6_3_1"> Halts
</label>
</div>
<span id="answer_798c34e297ea4272a061922af29366b6_3_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_798c34e297ea4272a061922af29366b6_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_798c34e297ea4272a061922af29366b6_solution_2"/>
</div><p style="padding-left:30px;"> \[ 0 \: \_ \: 1 \: R \: 1 \] </p>
<p style="padding-left:30px;"> \[ 1 \: \_ \: 1 \: R \: 2 \] </p>
<p style="padding-left:30px;"> \[ 2 \: \_ \: 1 \: R \: 3 \] </p>
<p style="padding-left:30px;"> \[ 3 \: \_ \: 1 \: R \: 4 \] </p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 3" role="group"><div class="choicegroup capa_inputtype" id="inputtype_798c34e297ea4272a061922af29366b6_4_1">
<fieldset aria-describedby="status_798c34e297ea4272a061922af29366b6_4_1">
<div class="field">
<input type="radio" name="input_798c34e297ea4272a061922af29366b6_4_1" id="input_798c34e297ea4272a061922af29366b6_4_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="798c34e297ea4272a061922af29366b6_4_1-choice_0-label" for="input_798c34e297ea4272a061922af29366b6_4_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_798c34e297ea4272a061922af29366b6_4_1"> Doesn&#8217;t halt
</label>
</div>
<div class="field">
<input type="radio" name="input_798c34e297ea4272a061922af29366b6_4_1" id="input_798c34e297ea4272a061922af29366b6_4_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="798c34e297ea4272a061922af29366b6_4_1-choice_1-label" for="input_798c34e297ea4272a061922af29366b6_4_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_798c34e297ea4272a061922af29366b6_4_1"> Halts
</label>
</div>
<span id="answer_798c34e297ea4272a061922af29366b6_4_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_798c34e297ea4272a061922af29366b6_4_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_798c34e297ea4272a061922af29366b6_solution_3"/>
</div><p style="padding-left:30px;"> \[ 0 \: \_ \: 1 \: R \: 1 \] </p>
<p style="padding-left:30px;"> \[ 1 \: \_ \: 1 \: R \: 2 \] </p>
<p style="padding-left:30px;"> \[ 2 \: \_ \: 1 \: R \: 3 \] </p>
<p style="padding-left:30px;"> \[ 3 \: \_ \: 1 \: R \: 0 \] </p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 4" role="group"><div class="choicegroup capa_inputtype" id="inputtype_798c34e297ea4272a061922af29366b6_5_1">
<fieldset aria-describedby="status_798c34e297ea4272a061922af29366b6_5_1">
<div class="field">
<input type="radio" name="input_798c34e297ea4272a061922af29366b6_5_1" id="input_798c34e297ea4272a061922af29366b6_5_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="798c34e297ea4272a061922af29366b6_5_1-choice_0-label" for="input_798c34e297ea4272a061922af29366b6_5_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_798c34e297ea4272a061922af29366b6_5_1"> Doesn&#8217;t halt
</label>
</div>
<div class="field">
<input type="radio" name="input_798c34e297ea4272a061922af29366b6_5_1" id="input_798c34e297ea4272a061922af29366b6_5_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="798c34e297ea4272a061922af29366b6_5_1-choice_1-label" for="input_798c34e297ea4272a061922af29366b6_5_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_798c34e297ea4272a061922af29366b6_5_1"> Halts
</label>
</div>
<span id="answer_798c34e297ea4272a061922af29366b6_5_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_798c34e297ea4272a061922af29366b6_5_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_798c34e297ea4272a061922af29366b6_solution_4"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Problem 3" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_798c34e297ea4272a061922af29366b6" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_798c34e297ea4272a061922af29366b6">
<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="798c34e297ea4272a061922af29366b6-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="798c34e297ea4272a061922af29366b6-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="798c34e297ea4272a061922af29366b6-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="True">
<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@4405fccb903345588493bd0872349e70">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-init="XBlockToXModuleShim" data-has-score="True" data-runtime-version="1" data-graded="True" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@4405fccb903345588493bd0872349e70" data-runtime-class="LmsRuntime" data-block-type="problem" data-request-token="2940f144028611efb5ee02329aca76dd" data-course-id="course-v1:MITx+24.118x+2T2020">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_4405fccb903345588493bd0872349e70" class="problems-wrapper" role="group"
aria-labelledby="4405fccb903345588493bd0872349e70-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@4405fccb903345588493bd0872349e70" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@4405fccb903345588493bd0872349e70/handler/xmodule_handler"
data-problem-score="0.0"
data-problem-total-possible="20.0"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="4405fccb903345588493bd0872349e70-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@4405fccb903345588493bd0872349e70-problem-progress" tabindex="-1">
Problem 4
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@4405fccb903345588493bd0872349e70-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><p>For each of the following descriptions, determine whether there could be a Turing Machine satisfying that description.</p>
<p><br/>A Turing Machine \(M\) such that given the code of a Turing Machine \(M'\) as input, \(M\) behaves as follows:</p>
<p style="padding-left:60px;">\(M\) outputs a \(1\) if \(M'\) halts when run on an empty input;</p>
<p style="padding-left:60px;">\(M\) outputs a \(0\) if \(M'\) doesn't halt when run on an empty input.</p>
<div class="choicegroup capa_inputtype" id="inputtype_4405fccb903345588493bd0872349e70_2_1">
<fieldset aria-describedby="status_4405fccb903345588493bd0872349e70_2_1">
<div class="field">
<input type="radio" name="input_4405fccb903345588493bd0872349e70_2_1" id="input_4405fccb903345588493bd0872349e70_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="4405fccb903345588493bd0872349e70_2_1-choice_0-label" for="input_4405fccb903345588493bd0872349e70_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_4405fccb903345588493bd0872349e70_2_1"> Yes
</label>
</div>
<div class="field">
<input type="radio" name="input_4405fccb903345588493bd0872349e70_2_1" id="input_4405fccb903345588493bd0872349e70_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="4405fccb903345588493bd0872349e70_2_1-choice_1-label" for="input_4405fccb903345588493bd0872349e70_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_4405fccb903345588493bd0872349e70_2_1"> No
</label>
</div>
<span id="answer_4405fccb903345588493bd0872349e70_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_4405fccb903345588493bd0872349e70_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_4405fccb903345588493bd0872349e70_solution_1"/>
</div><p><br/>A Turing Machine \(M\) such that given the code of a Turing Machine \(M'\) as input, \(M\) behaves as follows:</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><p style="padding-left:60px;">\(M\) halts if \(M'\) halts when run on an empty input;</p>
<p style="padding-left:60px;">\(M\) doesn't halt if \(M'\) doesn't halt when run on an empty input.</p>
<div class="choicegroup capa_inputtype" id="inputtype_4405fccb903345588493bd0872349e70_3_1">
<fieldset aria-describedby="status_4405fccb903345588493bd0872349e70_3_1">
<div class="field">
<input type="radio" name="input_4405fccb903345588493bd0872349e70_3_1" id="input_4405fccb903345588493bd0872349e70_3_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="4405fccb903345588493bd0872349e70_3_1-choice_0-label" for="input_4405fccb903345588493bd0872349e70_3_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_4405fccb903345588493bd0872349e70_3_1"> Yes
</label>
</div>
<div class="field">
<input type="radio" name="input_4405fccb903345588493bd0872349e70_3_1" id="input_4405fccb903345588493bd0872349e70_3_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="4405fccb903345588493bd0872349e70_3_1-choice_1-label" for="input_4405fccb903345588493bd0872349e70_3_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_4405fccb903345588493bd0872349e70_3_1"> No
</label>
</div>
<span id="answer_4405fccb903345588493bd0872349e70_3_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_4405fccb903345588493bd0872349e70_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_4405fccb903345588493bd0872349e70_solution_2"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Problem 4" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_4405fccb903345588493bd0872349e70" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_4405fccb903345588493bd0872349e70">
<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="4405fccb903345588493bd0872349e70-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="4405fccb903345588493bd0872349e70-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="4405fccb903345588493bd0872349e70-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="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-5" data-id="block-v1:MITx+24.118x+2T2020+type@problem+block@0b23433bc62c49799aa4e5bf90a96acf">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-init="XBlockToXModuleShim" data-has-score="True" data-runtime-version="1" data-graded="True" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@0b23433bc62c49799aa4e5bf90a96acf" data-runtime-class="LmsRuntime" data-block-type="problem" data-request-token="2940f144028611efb5ee02329aca76dd" data-course-id="course-v1:MITx+24.118x+2T2020">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_0b23433bc62c49799aa4e5bf90a96acf" class="problems-wrapper" role="group"
aria-labelledby="0b23433bc62c49799aa4e5bf90a96acf-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@0b23433bc62c49799aa4e5bf90a96acf" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@0b23433bc62c49799aa4e5bf90a96acf/handler/xmodule_handler"
data-problem-score="0.0"
data-problem-total-possible="10.0"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="0b23433bc62c49799aa4e5bf90a96acf-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@0b23433bc62c49799aa4e5bf90a96acf-problem-progress" tabindex="-1">
Problem 5
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@0b23433bc62c49799aa4e5bf90a96acf-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_0b23433bc62c49799aa4e5bf90a96acf_2_1">
<fieldset aria-describedby="status_0b23433bc62c49799aa4e5bf90a96acf_2_1 description_0b23433bc62c49799aa4e5bf90a96acf_1_1">
<legend id="0b23433bc62c49799aa4e5bf90a96acf_2_1-legend" class="response-fieldset-legend field-group-hd">Could there be a function \(f\) such that, for some distinct numbers \(n\) and \(m\), \(n\) and \(m\) both code Turing Machines that compute \(f\)?</legend>
<p class="question-description" id="description_0b23433bc62c49799aa4e5bf90a96acf_1_1">Again, assume the coding system described in ''Numbering Turing Machines'', <a href="/courses/course-v1:MITx+24.118x+2T2020/jump_to_id/6ae42c64326d471cb0899557527829c2">above</a>.</p>
<div class="field">
<input type="radio" name="input_0b23433bc62c49799aa4e5bf90a96acf_2_1" id="input_0b23433bc62c49799aa4e5bf90a96acf_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="0b23433bc62c49799aa4e5bf90a96acf_2_1-choice_0-label" for="input_0b23433bc62c49799aa4e5bf90a96acf_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_0b23433bc62c49799aa4e5bf90a96acf_2_1 description_0b23433bc62c49799aa4e5bf90a96acf_1_1"> Yes
</label>
</div>
<div class="field">
<input type="radio" name="input_0b23433bc62c49799aa4e5bf90a96acf_2_1" id="input_0b23433bc62c49799aa4e5bf90a96acf_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="0b23433bc62c49799aa4e5bf90a96acf_2_1-choice_1-label" for="input_0b23433bc62c49799aa4e5bf90a96acf_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_0b23433bc62c49799aa4e5bf90a96acf_2_1 description_0b23433bc62c49799aa4e5bf90a96acf_1_1"> No
</label>
</div>
<span id="answer_0b23433bc62c49799aa4e5bf90a96acf_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_0b23433bc62c49799aa4e5bf90a96acf_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_0b23433bc62c49799aa4e5bf90a96acf_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Problem 5" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_0b23433bc62c49799aa4e5bf90a96acf" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_0b23433bc62c49799aa4e5bf90a96acf">
<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="0b23433bc62c49799aa4e5bf90a96acf-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="0b23433bc62c49799aa4e5bf90a96acf-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="0b23433bc62c49799aa4e5bf90a96acf-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="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
© All Rights Reserved