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<sub>accept</sub> 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<sub>accept</sub> ) `}

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<sup>n</sup> | 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 !