CSCI 161 - Unit 3

COROLLARY 3.15

A language is Turing-recognizable if and only if some multitape Turing machine recognizes it.

PROOF
A Turing-recognizable language is recognized by an ordinary (single-tape) Turing machine, 

which is a special case of a multitape Turing machine.

That proves one direction of this corollary.

The other direction follows from Theorem 3.13.

After introducing Turing machines, how does our Chomsky hierarchy look like?

What are some decision problems that TM's can't do? 

1. Detecting infinite loops
   • Part of corecognizable languages
   • Can identify all no answers
2. Halting problem
   • Given a program and some input, can I determine for sure whether or not the program will eventually terminate
   • Part of recognizable languages
     • Recognizable b/c it can detect all yes answers
     • Not decidable b/c also able to detect no answers
     • Could be used to construct a self contradicting machine?

For nonrecognizable/noncorecognizable languages, we use the Turing equivalence to show that

• can't recognize two Turing machines as the same

Do we care about efficiency? Can we still focus on decision problems?

No. We care about trying everything to figure out what works. This means we focus on decision problems and in particular, decidable languages.

When is a language Turing-recognizable?

THEOREM 3.21

A language is Turing-recognizable if and only if some enumerator enumerates it.

PDAs can do addition; why can't they do multiplication but Turing machines can?

Turing machines have better memory access than PDAs where you can go back and fourth with your memory stack and your input.

Lets say we multiply 1^a with 1^b to equal 1^ab

• The idea is that we have 1^ab already given
• By checking the number of a times we see chunks of b, we can confirm the correct answer for 1^ab

What is a decider?

A nondeterministic Turing machine where all branches halt on all inputs.

What is the formal definition of a Turing machine?

A Turing machine is a 7-tuple where

M = (Q,Σ,Γ,δ,q0,qaccept,qreject) with
Q: finite set of states
Σ: finite input alphabet with the empty character not allowed 
Γ: finite tape alphabet that must include the input alphabet with the empty character (can include other symbols)
q0, qaccept, qreject: states that are the start, accept, and reject states respectively and with qaccept unable to equal the qreject state
δ: Q x Γ -> Q x Γ x { L, R } is the transition function

If we want to see delta in action, here's how it looks like with our previous example 

Here's how you read them

δ(q0,1) = (q1,x,R)
At state q0 when we read a 1, we transition to state q1, we replace 1 with x, and we move right on the memory tape

In our previous examples, this is how it looks like.

After introducing Turing machines, how does our Chomsky hierarchy look like?

What is a Turing Machine in practice?

Turing machines can simulate all the behaviors of a real life modern computer.

Since some machines are programmed to handle certain languages, Turing machines can be pre-programmed computers.

We can also think of Turing machines as algorithms in computers and software.

Are we gonna have a Turing pumping machine?

No. We will have something more complicated. 

What is a Turin-recognizable language?

What is a decidable language?

A language is called Turing-recognizable if some Turing machine recognizes it.

A language is decidable if some Turing machine decides it.

Design a Turing machine that does multiplication

First, how do we describe multiplication checking?

• We do checking since we're working with a decision problem
• The expressions we're looking at are possibly correct multiplication expressions with the answers already written

The first thing we describe multiplication checking is 

• at the highest possible level

In our computational model, we would assume the multiplication expression we're trying to check

• lives on some portion of the memory tape that we assume extends indefinitely to the right of where the input is written

Our algorithm that we will design will not need any portion of the tape that doesn't already start with the input on it.

Checking at a high level, we will naturally have a nested for loop. We will have something like this

• for each of the 1's before *
  • We will mark it
    • for each of the 1's between * and =
      • We will mark it and the next unmarked 1 after =
    • Restore all the 1s between * and = after marking all of them
• if there are no 1s left unmarked after =, we accept

The idea here is that we mark the number of 1's after the = by the amount of 1's on the right of * and repeat it by the number of 1's to the left of *.

We accept input that marks all the 1's to the right of =.

We leave the empty memory characters alone. They indicate that we reached the end of our input and we can accept our string.

Transitioning from high level pseudocode, we have the following low level pseudo code.

From here we can build a state machine to check our multiplication.

The idea here is when we begin at q0,

1. if we read a 1, we replace it with an x, and we move to the right of * to our first 1 and we move to qn (mark 1 from the first part)
2. At qn,
   1. with 1->R, we are replacing a 1 with a 1 since there's nothing to replace and loop there (passing through the 1's on the left of *)
   2. If we read a *, we replace * with * to move right and reach the looping state (passing *)
3. At the looping state
   1. If we read a 1, we replace it with an x, and we move right and move to the next state B0 (marking 1 from the second part)
   2. If we read an =, we replace it with an = and we move left and move to state C0 (all our 1's on the second part are marked)
   3. If we read a x, we replace it with a x and we move Right (passing all the marked 1s)
4. At B0
   1. If we read a 1, we replace it with a 1 and we move right (move past all the 1s)
   2. If we read an =, we replace it with = and we move right and we move to B1 (move past = to first 1)
5. At B1
   1. If we read an x, we replace it with an x and we move right (move past all the marked 1's)
   2. If we read a 1, we replace it with an x and we move Left and we move to B2 (mark the 1 in the third part)
6. At B2
   1. If we read an x, we replace it with an x and we move left (move back towards = passing all marked 1's in the third section)
   2. If we read an =, we replace it with = and we move left and we move to B3 (moving past the =)
7. At B3
   1. if we read a 1, we replace it with a 1 and we move Left (passing all the 1s in the second section)
   2. If we read an x, we replace it with an x and we move right and we return to the looping state where our first x was introduced (reaching a marked 1 in the second part)
8. At C0
   1. If we read an x, we replace it with a 1 and we move left (restoring all the 1s in the second part)
   2. If we read a *, we replace it with * and move left and move to C1 (passing the *'
9. At C1
   1. If we read a 1, we replace it with 1 and we move left (moving past the 1s in the first part)
   2. If we read an x, we replace it with x and we move right and we move to q0 (start over with the next unmarked 1 in the first part)

Notice there's no accept state yet. Let's create one

• Once we have marked all our 1's on the first part, we end up at * 
  • We transition to a state q2 and move right (to the first 1 in the second part)
    • If we read a 1, we move right (passing the 1's in the second part)
    • If we read an =, we move right and transition to a state q3 (passing the equal sign)
  • At q3
    • if we read an x, we move right (passing the marked 1s in the third section)
    • if we read the empty symbol, we move right and transition to the accept state (passing the first empty character)

Our machine doesn't know when something bad happens like a bad string

• If we have an extra 1 on the third part when we multiplied 2*3, it would equal 7
  • We would want to reject the input
• If we didn't specify any other rules at a certain state
  • We would reach a reject state

We have the Chomsky hierarchy where we introduce Decidable languages.

In Regular Languages:

• Say we have a language L where

L = {1^a + 1^b}

• We don't have any control over the a and b so we're just generating random 1's
• We don't have a memory stack as well
• We can build a DFA for this language

In Context free languages:

• We have a language L2 where

L2 = {1^a + 1^b = 1^(a+b)}

• We have a memory stack that we use to count the number of 1's from a and b to concatenate together.
• We also know that this language is not regular since we can't pump either 1 from the left side of the equal sign and match with the right side
• We can create a PDA with this language

Decidable Languages:

• We have a language L3 where

L3 = {1^a * 1^b = 1^ab } 

• With Turing Machines, we work with both the input and memory stack where we go back and fourth checking if our 1^ab is correct instead of just left to right check
• We can do complicated matching
• We know this isn't a PDA b/c it fails CF pumping lemma since pumping a 1 before and after the equal sign gives you less 1's on the right.
• Compared to PDAs, Turing machines have better memory access shifting left to right

Before we build the Turing machine, let's go back to the TSP:

• We have three cities with three edges with weights 1, 2, and 3
• We are looking for a target distance 6
• Since going through all the cities is of distance 6, we know 6 is an answer to the TSP
• If we have n cities to consider, we need to consider an n exponential amount of possible routes and see if there is a shorter path

In Turing machines, we don't care about efficiency. We care about getting our machine to work.

This means we can focus on decision problems. In particular, we will work with decidable languages.

Decidable languages:

• Every input can be given a yes or no label by a Turing machine that decides whether or not the input is in the language
• TSP, multiplication, and DFA equivalence are part of these languages

What is a multi-tape Turing machine?

' A multitape Turing machine is like an ordinary Turing machine with several tapes.

Each tape has its own head for reading and writing.

1. 1st tape appears in the input while the rest are blank
2. We can read, write, and move heads on some or all the tapes simultaneously

Our transition function will be 

• δ : Q × Γk−→Q × Γk × {L, R, S} where
  • k is the number of tapes

We read expressions like 

• δ(qi, a1, . . . , ak) = (qj , b1, . . . , bk,L, R, . . . ,L)
  • if the machine is in state qi and heads 1 through k are reading symbols a1 to ak
    • the machine goes to state qj , writes symbols b1 through bk, and directs each

 head to move left or right, or to stay put, as specified.

COROLLARY 3.18

A language is Turing-recognizable if and only if some nondeterministic Turing machine recognizes it.

PROOF Any deterministic TM is automatically a nondeterministic TM, and soone direction of this corollary follows immediately. The other direction follows from Theorem 3.16.

Illustrate the robustness of the Turing machine

In our Turing machine definition, the transition function forces the head to move to the left or right on the tape after each step

• The head can't stay still

If we allow the head to stay still

• The transition function would then have the form δ : Q×Γ−→Q×Γ×{L, R, S}.

This feature won't improve the power of other Turing models since we can transition left then right.

To show that two Turing models are equivalent

we simply need to show that one can simulate the other

THEOREM 3.16

Every nondeterministic Turing machine has an equivalent deterministic Turing machine.

PF idea:

simulate any nondeterministic TM N with a deterministic TM D

• have D try all possible branches of N’s nondeterministic computation
  • If D finds accept state, D accepts
  • Else, D’s simulation will not terminate
• view N’s computation on an input w as a tree
  • Each branch = nondeterminism 
  • Each node = config of N
  • Tree root = start config
• D searches this tree for an accepting configuration
  • Carefully needs to be done
  • Depth-first search doesn't work since we can go down an infinite branch
  • Breadth-first search explores all branches in the same depth and moves down once 

                    it has explored all of them 

• D will be able to visit every node in the tree until we find an accepting configuration

What are variants of the Truing machine?

Alternative definitions of Turing machines including

• versions with multiple tapes
• with nondeterminism

The original model and its reasonable variants all have the same power—

• they recognize the same class of languages

What is a nondeterministic Turing machine?

It has the same definition as the Turing machine except

• δ : Q × Γ→P(Q × Γ × {L, R})

We can think of a tree whose branches correspond to different possibilities for the machine.

If some branch of the computation leads to the accept state, the machine accepts its input.

What is robustness?

invariance to certain changes

Examples

• FAs and PAs are somewhat robust
• Turing machines are very robust

When is a language decidable?

COROLLARY 3.19

A language is decidable if and only if some nondeterministic Turing machine decides it.

How does an enumerator work?

An enumerator E starts with a blank input on its work tape.

• If the enumerator doesn’t halt, it may print an infinite list of strings

The language enumerated by E 

• is the collection of all the strings that it eventually prints out

E may generate the strings of the language in any order, possibly with repetitions.

What is an enumerator?

A Turing machine variant that can be loosely defined as a TM with an attached printer.

• Printer = output device to print strings
• Every time the Turing machine wants to add a string to the list, it sends the string to the printer

Are multi-tape Turing machines equivalent to ordinary Turing machines?

THEOREM 3.13

Every multitape Turing machine has an equivalent single-tape Turing machine.