## Turing-machines

Question 1 |

(a) Show that Turing machines, which have a read only input tape and constant size work tape, recognize precisely the class or regular languages.

(b) Let L be the language of all binary strings in which the third symbol from the right is a_{1}. Give a non-deterministic finite automaton that recognizes L. How many states does the minimized equivalent deterministic finite automaton have? Justify your answer briefly?

Theory Explanation. |

Question 2 |

A is recursive if both A and its complement are accepted by Turing machines.

True | |

False |

Question 2 Explanation:

If A is decidable, then A and A' are accepted by Turing machine.

Question 3 |

Which of the following is/are undecidable?

Given two Turing machines M1 and M2, decide if L(M1)=L(M2). | |

Given a Turing machine M, decide if L(M) is regular. | |

Given a Turing machine M, decide if M accepts all strings. | |

Given a Turing machine M, decide if M takes more than 1073 steps on every string. |

Question 3 Explanation:

Equality problem of recursively enumerable languages is undecidable, so whether two Turing machines accept the same language is undecidable.

Checking whether a Turing machine accepts a regular language is also undecidable.

Completeness problem for recursively enumerable language is undecidable thus whether a Turing Machine accepts all strings is undecidable.

Whether a Turing machine takes more than 1073 steps is decidable as we need to run the Turing Machine only for 1073 steps so no chance of going into an infinite loop hence it is decidable.

Checking whether a Turing machine accepts a regular language is also undecidable.

Completeness problem for recursively enumerable language is undecidable thus whether a Turing Machine accepts all strings is undecidable.

Whether a Turing machine takes more than 1073 steps is decidable as we need to run the Turing Machine only for 1073 steps so no chance of going into an infinite loop hence it is decidable.

Question 4 |

Which of the following is FALSE with respect to possible outcomes of executing a Turing Machine over a given input?

it may halt and accept the input | |

it may halt by changing the input | |

it may halt and reject the input | |

it may never halt |

Question 4 Explanation:

→ The halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running (i.e., halt) or continue to run forever.

→ Halting of Turing machine is an undecidable problem. A general algorithm to solve the halting problem for all possible program-input pairs cannot exist.

→ Possible outcomes are

1. It may halt and accept the input.

2. It may halt and reject the input.

3. It may never halt.

→ Halting of Turing machine is an undecidable problem. A general algorithm to solve the halting problem for all possible program-input pairs cannot exist.

→ Possible outcomes are

1. It may halt and accept the input.

2. It may halt and reject the input.

3. It may never halt.

There are 4 questions to complete.