cs701 Assignment No. 1 Solution and comment Due Date: 18 November, 2016

CS701 – Theory of Computation

Assignment No.1

                                      Maximum marks: 50

                                                                                        Due Date: 18 November, 2016

Instructions

     

The purpose of this assignment is to give you hands on practice. It is
expected that students will solve the assignments themselves. Following
rules will apply during the evaluation of assignment.

·         Cheating from any source will result in zero marks in the
assignment.

·         Any student found cheating in any of the two assignments submitted
will be awarded "F" grade in the course.

·         No assignment after due date will be accepted through email

Question No. 1 (12+8+5=25 marks)

Describe and Design a Turing machine in following three ways description that decide the following language

1.         Formal description of Turing machine

2.         Implementation level descriptions of Turing machine

3.         High level description of Turing machine

a) L = {1³ⁿ:  n≥1}, the language consisting of all strings of 1s in given exponential function. Some example words of the language are as follows:

a.         111

b.         111111111

c.         11111111111111111111111111

Question No. 3 (9+8+8=25 marks)

Read the research paper entitled “The Turing Machine May Not Be the Universal Machine” and answer the following questions:

1)      How can you differentiate between Turing machine and Universal machine as discussed in the paper?

2)      What types of human and computer relation has been analyzed in the paper? Discuss it with help of given figures in the paper.

3)      Write the critical review of this paper?

Please download above Research paper which has attached with assignment file on zip file.

Note:

Plagiarism will be checked for each question. Please answer the questions in your own words and marks will be awarded on the basis of your answer and plagiarism report.

For any query about the assignment, contact at CS701@vu.edu.pk