Theory of Computation (Cs701) Assignment

Virtual University MS (CS), Fall 2017

CS701 – Theory of Computation

Maximum marks: 50                                                          

Question No. 1:

Part 1.) Suppose we will take a following Diophantine equation as an input, show that given equation has solution in positive integers.

Solution Part1:

Equation  33x+15y=14

                        HCF=    (33,15)

                              (i)           33= 2 x 15 + 3

(ii)          15= 3 x 5 + 0

We can write them as

3= 33- 2 x 15

3= 33(1) +15 (-2)

3= 33x + 15 (y)

It means that                      x= 1

And                       y= -2

It is proved that the given equation has no positive solution.

Q#1: Part 2

Draw the Turing machine for  0³ⁿ⁺¹

Turing Machine of 0³ⁿ⁺¹ will be as under

The machine will accept the string 000

The machine will not accept any language except cube of zero as shown below:

Question No. 2:

1)     How can you differentiate and analysis between Turing Machine and Fuzzy Turing Machine as discussed in the paper? Elaborate it critically in your own words

v In classical computability theory it is important that there should be a universal turing machine unfortunately there is no universalFuy turing exist that is draw back of fuzzy Machine. But universal turing machines exist.

v Fuzzy machines are not adequate to represent fuzzy computability.

v Fuzzy Machines are more powerful than Turing machines.

v A fuzzy machine is not perfect to compute fuzzy theory.

v A Turing Machine is a perfect machine in every aspect.

2)     What functionalities have been expressed in extended Church thesis? Elaborate it critically in your own words.

After examining thoroughly the mathematical proves described in the research paper it is clear that the fuzzy machine has several limitations and it will not be a good decision to propose for this machine a thesis analogous.

It is also expressed in the paper that fuzzy machine is not enough to represent fuzzy computability.