Reference no: EM133143072

Question:

(a) Construct a Turing Machine that on input 0ⁿ, i.e. n zeros, outputs the number n in binary.

There is no need to give the precise transition function - you should explain how the machine works in plain English. You may use multiple tapes in your machine.

(b) Consider the problem of determining whether two Turing Machines A and B decide different languages. Prove that this problem is ni-complete.

(c) Fix the tape language of a Turing Machine to be {0, 1, U} Let f (n) be the maximum number of steps that any Turing Machine with n states makes before it terminates when ran on the empty input. Are there computable functions g (n) and h (n) such that g (n) ≤ f (n) ≤ h(n) for every n? Justify your answers. If h or g exists, provide a good lower or upper bound, respectively. The better bounds you give, the higher mark you will get.

(b) The weight of a cycle in an undirected graph with positive edge weights is defined as the sum of the weights of the edges in the cycle.

SMALL WEIGHT CYCLE

Instance: an undirected graph G = (V, E) with positive weights on its edges, a path P in C, and a positive integer k. Question: does C contain a cycle that includes all the edges of the path P and has weight at most k?

LARGE WEIGHT CYCLE
Instance: an undirected graph C = (V. E) with positive weights on its edges, a path P in C, and a positive integer k. Question: does C contain a cycle that includes all the edges of the path P and has weight at least k?

i. Provide a polynomial algorithm (without writing any pseudocode) and prove its correctness for Low WEIGHT CYCLE.

ii. Describe a polynomial-time reduction from HAMIUMNIAN CYCLE to LARGE WEIGHT CYCLE and prove its correctness.