## 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