# Theory of Computation Assignment 1

## Question 1

It is possible to offer another algorithm to decide the language A of example 3.7:

In any step we delete the right half of the 0-s that are still written on the tape. We continue with this process until we reach a point at which the number of 0-s is odd and greater than 1 - Which is rejected, or until we reach a single zero - which is accepted.

Present a **full description** of a Turing Machine that implements the algorithm (as in figure 3.8 in the book).

The tape alphabet is: Γ = {0,x , ⌴ }

The machine won’t have more than **10**** states (**including *q _{accept}* and

*q*)

_{reject }**Explain well** the machine operation and why it indeed decides the language A.

## Question 2

Build a Turing Machine that when it receives as input the word ‘w’ above the alphabet {0,1}, it is ending in a state *q _{accept}* and on the tape the word ‘w’ is written and afterwards

0-s as the number of 0-s in ‘w’.

For example, if: w=0110010, then at the end of the run, on the tape the word 01100100000 will be written.

Input alphabet is Σ={0,1}, Tape alphabet is Γ = {0,1 , ⌴ } The machine won’t have more than **10** ** states (**including *q _{accept }*)

Comment: The machine won’t have a *q _{reject}* state.

Describe the machine with a figure.

**Explain well** the machine operation and why it indeed follows the requirements. Remember to handle correctly the case in which ‘w’ is the empty word.

Pay attention that the tape alphabet is Γ = {0,1 , ⌴ }

## Question 3

- What is the language that the machine you build in question 2
**recognizes**? B. What is the function the machine you build in question 2**computes**?

## Question 4

We will observe the following computation module: Turing Machine **with infinite states** . This machine is identical to a regular machine. Accept that the number of states could be infinite.

Does this machine have more computational power than a regular machine?

If you answered ‘yes’, show that a machine with infinite states can recognize languages that can’t be recognized with a machine that has a finite number of states. In addition, explain why the existence of such a machine doesn’t contradict the Church-Turing Thesis.

If you answered ‘no’, show how a machine with a finite number of states could imitate the operation of a machine with an infinite number of states.

## Question 5

A natural number is called *composite * if it is not a prime number (which means, equals 1, or has other dividers except 1 and itself).

- Describe a nondeterministic Turing Machine to decide the following language F:

F = {*a ^{n }*| n≥1; n is composite }

The detail level of the description should be similar to the machine *M*_{3} from example 3.11 in the book.

The machine should use nondeterminism in a way that would ease the computations (In comparison to a deterministic machine for the same task). Pay attention: The machine you describe **decides ** the language (and not just recognizes it).

- Assuming we swap in the machine you suggested between the states
*q*and_{accept}*q*, what is the deciding language in the new machine?_{reject}

**Explain well** your answer.

## Question 6

Build an enumerator to language A of example 3.7.

The alphabet Σ of the output tape will be {0}, the alphabet Γ of the work-tape will be

Γ = {0,x , ⌴ }

The enumerate **won’t have more than 8 states****(** including *q**halt* and *q**print *)

Describe in enumerator using a figure (as the figure 3.10 in the book, no need to include *q _{halt }*and all the edges that enter it. No need to draw impossible transitions).

**Explain well **how the enumerator works and why it indeed enumerates the language A.

## Question 7

Language L is a non trivial language above alphabet Σ (L≠⊘ and L≠ Σ^{* })

An **Alternate Enumerator ** for language L is an enumerator that prints an infinite series of words: w1, w2, … in which:

- L = {w1,w3,w5…}
*L*= {w2, w4, w6 ...}

In other words, the enumerator prints one time a word which belongs to L and afterwards a word which doesn’t belong to L.

Every word in Σ^{* }eventually is printed, since any such word either belongs to L or not.

It is possible to have words printed more than one time.

- Given that a language L has an alternate enumerator, Does L
**must**be a**decidable**language?**Prove**! - Given that a language L is a non trivial language and
**decidable,**Does L**must**have an alternate enumerator?**Prove**!