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

17.2: Turing Machine Execution
- Defining an Execution Model for a Turing Machine

David Evans and Nathan Brunelle
University of Virginia
---

This is the definition of what it means to
execute a Turing machine.

And I've slightly modified the definition
that's in the book.

You can see there's a
bit of an issue discussion

about what the right
definition should be.

What it means to execute is we're trying
to get an output.

The value that we're
getting from executing a

machine that matters is
the output of that machine.

And we're going to find that output by
initializing the tape.

So this is where that special triangle
symbol is there.

That's going to be on the first square.

Then the rest of the squares are going to
be the input.

Each symbol in one square.

And then we get to the last input symbol.

And everything after that is blank.

We're executing it on some input.

So we've got to start by configuring the
tape to encode the input.

This is different from
our circuit models where

we encoded input as
input wires to the circuit.

Here we're using the scratch
paper that we can use in

the computation also as
the way to encode the input.

We're going to keep track of two
variables.

This is definitely a sort of informal way
of describing the model.

It's assuming things that are not really
always defined in mathematics.

These are variables that we're going to be
able to update.

We're changing their value.

But we're changing their value and we're
doing a loop.

So this assumes some
understanding of computing

that should make you
a little uncomfortable.

Because we're defining what's
supposed to be a mathematical

model using intuitive notions
of what a repeat loop means.

Okay.

And so at each step, we're
going to look up in the transition

function what s, which is
recording the current state.

And you can see s is initialized to zero.

So there's a special state zero,
which is always the state we started.

Some definitions of
turing machines have an

extra parameter,
which is the initial state.

But this definition says we'll always
start and say zero.

That's nice and simple.

What is the meaning of I?

Take a second to look at how we use i.

So I starts at zero.

We use I here.

And we update i.

This r is moving right.

We update i.

This l is moving left.

We update i.

Can you figure out what I is representing?

Yeah.

Yeah.

It's where we are on the tape.

I equals zero is the leftmost square.

As we operate, this is I equals zero.

This is going to be I equals one.

Each square has an index.

So as we move around on the tape, you can
think of a tape head moving left or right.

We update the value of i.

Initially, it's zero.

So we're starting here.

And then each step, we're going to look up
the transition function.

Remember, the transition function takes
two inputs.

It takes a state and a symbol.

So these are the three outputs that are
returned.

The new state, the new symbol,
and the direction.

And then we update the state.

We update the tape.

This is replacing what was there with some
new symbol.

If it had a new symbol.

And then we move.

The definition said the direction can be s
to stay.

That means I wouldn't change.

So we don't actually need to do anything
if it's s.

Are we done?

Are we happy with our definition of what
it means to execute a Turing machine?

So our transition function...

To define the machine, we have to define
the transition function.

And that tells us how to update the
machine.

Each step is taking one transition.

And we are using it right here.

In step one, in the repeat loop,
we are looking at our current I,

reading the symbol at that
square, looking at the output

of the transition function
to decide what to do next.

And the transition function
returns the next state,

the symbol to write,
and the direction to move.

So that's where we're using the transition
function.

What's missing from this definition?

Yeah, at the back?

Good, yeah.

So the whole point of defining this,
right?

What it means to execute is we get some
output.

We haven't said what the output is,
right?

We've said how we follow transitions.

We've said how we initialize the machine.

We need to get an output.

And getting the output is actually kind of
tricky.

So one way to get the
output, which is actually a very

reasonable way, is kind of
like the finite state machine.

So at the end, if you halt, you were in
some state.

Based on that state, you either output 0
or 1.

That's kind of how the finite state
machine output function was defined.

But the Turing machine, we've got a whole
tape.

So maybe we can output a lot more.

And certainly if we're thinking
of things like computing

numbers, we need to
output more than just 0 or 1.

So Turing's goal was to see can we output
something that represents a number.

So we're going to use the state of the
tape to learn the output.

And so that's what step four is here.

If we finish this loop, that
means that we get to some

transition rule where the
output direction is called.

Then we get to step four.

And step four says the output is what's on
the tape.

Except for we're going to ignore all the
blanks at the end.

We want the output to be finite and the
tape's infinite.

But at some point, everything to the right
of where we are is a blank.

And the way it's defined skips the first
square, which started as a triangle.

That kind of assumes you're not going to
overwrite that triangle.

It takes everything from the first square
up to the last square that's not a blank.

And that's our output.

Otherwise, the output is undefined.

And we use that bottom symbol to mean
undefined.

So it could be undefined because we never
finish this loop.

We only have an output if we get to step
four.

Yeah.

Question.

Ah, so yeah.

How do you know...

If you think of it like
this is an infinitely

long tape and it's
rolled up in some room.

And you've got to decide whether something
past where you are might be a blank.

And you see a million blanks.

You don't know that the next one would be
a blank.

Is there a way to know how far you have to
look?

Where's the furthest non-blank?

Yeah.

We said we start with I equals zero.

And each step, the most we could increase
I is by one.

We could decrease I or we could increase
I.

So if the machine runs for
a thousand steps, assume

we know the length of
the input is less than that.

Do we know if there are any non-blanks
after index a thousand?

It's sort of the max of the number of
steps in n.

Because we do start at zero.

It could take us n steps to get to the end
of the input.

If we run for less than n steps,
the input is still there.

But once we run for more than n steps,
that's all that matters.

We haven't ridden in
any squares further away

from where we started
than the number of steps.

Let's say s steps.

This definition makes sense, even if you
can't look at the whole tape.

If we had to do this in practice,
we can look at what we need.

Because we know how many steps we ran for.

We can keep track of that.

So we know that nothing beyond that can be
non-blank.

I'll point at the difference in the
definition from what's in the book.

The book is the smallest integer like
this.

And mine is the smallest integer where
it's a blank.

Do those definitions produce different
outputs?

Both of them, if there's a
blank in the middle, m will

still be higher than that if
there's a non-blank after it.

The question is more, this one will stop
at the last 0 or 1.

If there's, say, some other
symbol after those that's

not a 0 or 1, this definition
would not include it.

Whereas this one would include it.

So this one's going to include everything
before the last non-blank.

So if we're thinking of this as a function
that should output a string in 0,

1 star, if we have more
symbols, it's going to

output some strings
that it shouldn't output.

But this one also includes those.

It will include if
there's a funny symbol

before the last blank
it's going to include it.

So the definition I think is probably the
best is to actually just include all the

0s and 1s on the tape and ignore
everything else.

That's different from either of these.

But the good news is we don't have to
worry too much about that.

For a specific Turing machine,
if you're implementing one and you care

what the output is, you
definitely have to worry about

which definition of how you
get the output from the machine.

In terms of the big questions
that we're trying to use

these to model, it's not
going to make a difference.

This is how Turing actually
defined it, which is partly

why I like the let's just take
the 0s and 1s on the tape.

He had a notion of printing a
0 or 1 as you operate it, which

was kind of separate from the
tape, what you were printing.

You still had the tape that you could use
to keep track of things, and then you had

the output that you were printing on a
blank tape.

That is what he viewed as the output,
a separate tape that you print on,

which is not what we usually use today.

But this gets at the notion of what
computable numbers are, is if you can

output on that tape the sequence of 0s and
1s that represents the number,

then it's a computable number.

I can't use it.

It's not.

I will see you in the next step.

You can do it.