Theory of Computation

CS 3810, Spring 2020

Name:

Quiz 09.1

1. (T4) Prove the language given below is decidable.

Evens = {x | x is even}

2. (T5) Argue that the “improved” Turing machine model described below is not more powerful (in terms of computability) than a standard Turing machine.

Consider a “jumpy” Turing machine which is like a normal Turing machine in every way except the read/write head must move either two places to the right or three places to the left each time. Argue a jumpy Turing machine is equivalent in computational power to a standard Turing machine.

3. (T6) Provide a reduction from the subtraction of two numbers (a − b) to the problem of summing two numbers (x + y).

4. (T7) Prove the following language is undecidable by reduction from AT M or HALTT M.

EV ENT M = {〈M〉 | M is a Turing machine which accepts exactly all even numbers}