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

1. 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).

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

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

The detail level of the description should be similar to the machine M₃ 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). 

1. Assuming we swap in the machine you suggested between the states q_accept and q_reject , what is the deciding language in the new machine?

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 qhalt and qprint )

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.

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