---
Video Title: Turing Machine Examples
Description: Theory of Computation
https://uvatoc.github.io/week8

16.4: Turing Machine Examples
- MAJ pseudocode
- SAME pseudocode, state machine

Nathan Brunelle and David Evans
University of Virginia
---

So, I'm gonna talk about,
at a high level, how a.

Turing machine might
compute our zeros and ones.

So, the idea to compute this infinite
majority with a Turing machine.

We're gonna have a bunch of zeros and ones
on the tape.

That's going to be our input.

And the idea for what we're
going to do is we're gonna

sort of cross off every
single zero that's on our tape.

And, every time we cross off a zero,
we're also gonna cross off a one.

If we can mark off all the
zeros and still have leftover

ones, then that means the
majority were ones and we accept.

So for each zero, cross it off and also a
one with it.

If there's leftover ones, return one.

That is how we're going to do this.

Let's see some idea for how a Turing
machine might look while it's doing this.

So here our input is 0, 1, 1, 0,
1.

So we can see we have 0, 1, 1,
0, 1 preloaded on our tape.

Our Turing machine starts
out being in the very first cell

in that tape, the first memory
location in our memory tape.

The way this Turing
machine might work is we're

going to move right
continuously looking for a zero.

So we're going to keep moving right.

We're just going to
move right one spot at a

time until we see a
zero, and then we stop.

In this case, we're already at a zero,
so we're not going to do anything.

Once we find a zero, I'm
going to overwrite that symbol

zero with like a marked off
or a crossed out symbol zero.

In this case, we mark off that zero.

And then what we're going to do is we're
going to move right until we find a one.

Once we have found that one, we're going
to mark it off.

And then I'm going to go all the way back
to the beginning of the string.

So there we are, all the way back to the
beginning of the string.

And then I'm just going
to keep repeating one

through three until
there's no more zeros.

I've gone back to the beginning of the
three.

I'm going to look for a zero.

There it is.

So I mark it off.

Then I go back to the beginning of the
string.

And then I look for a one and mark it off.

And I go back to the beginning of the
string.

And I look for a zero.

And now I've found that there are no more
zeros.

This is something that we're going to call
a blank.

Preloaded onto our memory is our input,
where the rest of the infinite number of

locations in the tape we say are filled in
with blank symbols.

We have a special symbol that means this
memory unused.

So what we've done is we've gotten to a
blank, meaning there's no more zeros.

So what we're going to do next is go all
the way back to the beginning.

Check to see if we can find any more ones.

If we do, we return one.

Otherwise, we return zero.

We saw another one, so we're going to
return one.

So this is how a Turing machine would
compute this function.

A lot of the things we did here are kind
of difficult to see how they're going to

pan out, how they're actually going to
become a Turing machine.

So we're going to do a slightly simpler
function with this Turing machine.

Before I talk about the formal definition,
I'll do one more example.

I'm going to give a Turing machine for
this function same.

Where same is going to be
equal to one, if the bits have

this form where all of the zeros
come before all of the ones.

So x is going to be a bunch
of bits, and we want to say

all of the zeros in x come
before all of the ones in x.

And I have the same number of zeros as I
did with ones.

So for instance, 0, 0, 0, 1, 1,
1, we want to return one, because we have

all the zeros strictly before all of the
ones, with the same number of each.

Here, even though we
have the same number of

zeros as ones, the ones
came before the zeros.

This does not belong to same.

Here, even though we have the
same number of zeros and ones,

we didn't have all of the
zeros before all of the ones.

Some of the zeros and ones were out of
order.

So this does not belong to same.

In this case, even though we had all of
the zeros coming before all of the ones,

We didn't have the same number of each,
so it does not belong to same.

So let's give some
pseudocode for what our.

Turing machine is going
to do on this input same.

So I'm going to follow through what this
pseudocode is saying on some input.

So here we're going to have some input.

Let's do something where it's going to
accept.

So let's do 0011 should belong to this
input.

Everything after that 0011 is going to be
blank.

So we're going to start out looking at
this first location in memory,

so we're going to say if the current
character is blank, then accept.

0 is not blank, so we don't do this.

If the current character isn't 0,
then reject.

It is 0, so we don't do that.

Mark this 0.

I'm going to mark it by just sort of
crossing it out.

So that's now a crossed out 0 character.

Whatever that means.

So we mark that 0, and then we're going to
scan right until we find a 1.

Here we are, we have a one.

We are looking at this location in memory
now.

We are going to now mark this one.

There is a marked 1.

And then what we are going do is scan
until we see a blink.

If we see a zero, we reject.

We don't see a zero
before we get to the blink,

so we are going out until
we see a marked zero.

Try to keep going left, left, left,
left.

Here is a marked zero.

Then we are going to move right by one.

So now we are looking at this location in
memory.

Next we are going to...
let's see... until we see a

marked zero, then we are
going to move right by one.

And then we are going
to keep scanning right until

the next thing is something
other than a marked one.

Zero is something other than a marked one,
so we don't move.

And then we go back up to step one.

Is this a blank?

No.

Is it a non-zero?

No.

Therefore it must have been a zero,
so we are going to mark it.

We mark it.

Scan right until we find the next one.

We mark it.

Scan right until blank.

We found blank.

Scan left until we see a marked zero.

We have a marked zero.

Move right by one.

Scan until the next character isn't a
marked one.

That's a marked one, so we're going to go
right.

We go to step one.

If the current character is a blank,
then accept.

Hey, that was a blank.

So we're going to return one.

Just like we wanted to do.

So let's look at one more example.

We'll look at an example where we wanted
to reject.

So let's just do zero, zero, one,
let's say.

So we want to reject this one.

We don't have the same number of zeros and
ones.

So we're going to start out by looking at
this location in the memory.

If it's a blank accept, it's not.

If it's a non-zero reject, it's not a
non-zero.

So we're going to mark the zero.

Next, we're going to scan right until we
find a one.

We scanned and we found this one.

We're going to mark the one.

Scan right until we find a blank.

We didn't see a zero, so we don't reject.

Scan left until we see a marked zero.

So now we're over here at the marked zero.

Move right by one.

Now we're looking at a zero.

Scan right until the next character isn't
a marked one.

Zero isn't a marked one, so we don't move.

Go back to step one.

If the character is a blank accept,
it's not.

If it's a non-zero reject, it's not.

Mark the zero.

Scan right until we find the first one.

We are going to scan right.

We got to a blank, so we reject.

Just like we wanted to do.

Reject means return zero.

We got the right answer both of these
times.

I tried this for a lot of inputs.

I'm pretty sure it gives the right answer
every single time.

Let me know if there is some sort of
mistake.

This is super, super complicated.

Turing machines, even though they are so
simple, or basically because they are so

simple, programs you are going to write
with them often become very complicated,

very difficult to debug, and so forth.

It's hard to see why this works,
but I'm pretty sure that it does.

Let's draw this Turing machine.

When we draw a Turing machine,
we are going to have a finite state

automaton where the difference is going to
be what we do on the transitions.

All that finite state automaton did is
they said, depending on which bit you are

looking at and which state you are in, and
you are going to go to a different state.

With the Turing machine, instead of our
transitions just taking us from one state

to another, they are
going to take us from one

state to another while
also changing the memory.

We are going to take each one of these
steps that we see in this pseudocode,

and I am going to use
those to start drawing

the states and transitions
on a Turing machine.

The way that a transition on a Turing
machine is going to look is we are going

to have a transition from one state to
another where we are going to have the bit

that we are currently reading on the input
as the first thing we list on a

transition, the bit we are going to write
to the input.

So if we are going to change what is at
that current location of the input,

then we are going to change it to that
second symbol there.

And then how we are going to move on the
memory.

So that can be either move go left,
go right, or don't move at all.

Stay in the same spot.

So we are going to see three things per
transition.

What we need to read in order to take that
transition, what we are going to write

when we do, and how we are going to move
what memory location we are looking at.

What we are going to do is we have our
start state.

I am just going to go ahead and begin by
drawing our start state.

Just like with our finite state automata,
Turing machines have start states.

We are also going to have
our accept state where we

return one, and our reject
state where we return zero.

So I am just going to double circle this
to indicate whenever we enter this state

we return one, Whenever we enter the
reject state, we return zero.

So step one, if the current character is
blank, then accept.

So we're going to say, if we saw a blank,
then I'm going to write, I don't care what

to the tape, and I'm going to do no
movement.

So if we're currently looking at a blank,
we're going to read a blank, write a

blank, don't move, and transition to the
accept state.

If the current character isn't a zero,
then reject.

So we're going to have a transition to the
reject state.

We're basically going to say anything
that's not zero.

So if b is not zero, whatever that symbol
is, we're going to say, read the b,

write the b, and then don't move on the
tape.

And now we reject.

The next thing we're going to do is we're
going to say, mark the zero.

So if we don't do either of those things,
the only other option is to mark the zero.

So it must have been we were reading a
zero on the memory.

So we're going to change that zero to a
marked zero.

And then we're going to start scanning
right.

So we're going to move our memory right.

And our goal was that we wanted to keep
moving right until we saw a one.

So if we saw a zero, then we're not going
to change it and move right.

If we saw a marked
zero, then we're not going

to change it and we're
going to move right.

We're also eventually going to see marked
ones that I need to think about.

So if I see a marked
one, then I'm not going

to change it and I'm
going to move right.

I'm going to keep moving right until I see
a one.

If I saw a blank before I saw that one,
then I want to reject.

So I'm going to have this
transition that goes over here

that says, if I saw a blank,
then I'm going to reject.

I'm going to transition to the reject
state.

I will finish this machine out and post
that with these slides for this lecture.

But hopefully you can start to see kind of
how these Turing machines are behaving.