Sale!

# CENG 280 Homework 6 Solved

Original price was: \$40.00.Current price is: \$35.00.

Category:

5/5 - (1 vote)

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