Description
Question 1 (15 points)
Alan Turing was born in June 23 1912 and died in June 7 (i) .
Turing played a crucial role in breaking the (ii) code during World War II.
The now-famous (iii) , proposed in his paper Computing Machinery and Intelligence (1950),
is an attempt to define a standard for a machine to be called “intelligent”.
One of his most-cited works, titled (iv) was published in 1952, which
proposed a mechanism as to how inhomogeneous patterns in nature arise from symmetric starting states.
The 2014 movie titled (v) aims to give a biographical portrait of Turing.
Question 2 (50 points)
Give a semidecider for the language a
∗
ba∗
b by
a) Using the Formal Definition of TMs in our textbook 4.1.1.
Note: You are expected to provide a diagram/drawing of the resulting TM.
b) Using combination of Basic Machines e.g L, R, Ma etc.
Question 3 (35 points)
Integer Exponentiation. Construct a Turing machine that computes the integer exponentiation.
Your machine will have three tapes. The first tape will start with a and b, both represented in binary,
separated by a comma. The machine will compute a
b
in binary. You can assume you already have access
to and call Turing machines M+, M×, and M− which add, multiply, and subtract two numbers respectively.
Note: Your answer need not be, nor is expected to be formal. Just make sure that you define an algorithmic procedure computing a
b
. See the descriptions of the TMs in p.206 and p.225 in the textbook to get a
sense of the expected level of detail.
1
Note: You can assume any form of operation (such as where it takes the input from, or where it outputs
the computed quantity) for the Turing machines M+, M×, M−.
Specifications
• Deadline: The deadline for this homework is strict and no late submissions will be accepted.
Submission deadlines are not subject to postponement.
• Grading: “sufficiently reasonable” solutions will get full credit for the subject question,
even if it is partially incorrect. Rough criteria for a solution to be sufficiently reasonable are being
the student’s original answer and at least partially relying on a correct approach/method even if the
application is not totally correct.
• Cheating: Any type of cheating or extensive collaboration is strictly prohibited. In case of cheating,
the cheater’s all homeworks will be graded zero (0); further, university regulations about cheating
will be applied.
• Updates: Follow the course page on ODTUClass for any updates and clarifications. Please ask your
questions on ODTUClass instead of e-mailing if they do not contain some part of the solution. Otherwise, you can send an email to “bugra@ceng.metu.edu.tr” and/or “mferhata@ceng.metu.edu.tr”.
Submission
Submissions will be done via ODTUClass. You are expected to submit a single searchable/vectorized
PDF file named “HW6_yourStudentID.pdf (e.g. HW6_1234567)”. Submissions violating the naming
convention will be penalized. Also write your name and student ID number to the top of your solution
sheets. A grade reduction will be applied to the solution sheets without a name and ID on them.
2
