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

16.3: Turing Machines

Nathan Brunelle and David Evans
University of Virginia
---

So the next thing we're
going to talk about is something

that is everything we might
desire, which is Turing machines.

The advantage Turing machines give us is
memory.

Finite state automata, by this property
that we could only transition using the

current input bit and the current state,
finite state automata have no memory.

We don't remember how we got to where we
were, we just know that we're there now.

So it's everything that finite state
automata do, finite state automata,

they're kind of like goldfish.

Everything they do is purely a reflex.

Turing machines, though, have memory.

So for this majority function,
basically the reason finite state automata

couldn't compute majority was we needed to
count zeros.

The size of that count had to be
arbitrarily large.

As we had more and more and
more zeros, we were going to

need more and more and more
space to represent that count.

So finite state automata,
they have no memory, so we

have no place to write down
what our current count was.

Turing machines are going to give us this
memory.

This is going to be a
more powerful model of

computation than
finite state automata are.

Turing machines are
basically, you can think of

them as a finite state
automaton with memory.

So if we have a finite
state automaton, we slap

some memory on it,
we got a Turing machine.

Now I sound like a used car salesman.

With a Turing machine, we're
still going to have our finite

number of states just like we
have with finite state automata.

We're going to see
that there is a finite state

automaton sort of hidden
within a Turing machine.

But we're going to have
this extra thing available to

us, which we're going to
call a semi-infinite tape.

So we call it semi-infinite because it's
infinite in one direction.

So it's got a beginning but no end.

So here is our tape.

The tape has a bunch of different
positions in it where we can store a bit.

We have a first bit, we have no last bit.

We have no last position on this memory.

So our memory is this one-dimensional
memory that we're going to call a tape.

We have a bunch of locations in this
memory where we can store bits.

And what we're going to do is,
for a finite state automaton, we

transition using just the input bit and
the state.

For a Turing machine, we're
going to be able to transition

using the state and our
current symbol on the tape.

So we are able to use
what we are currently

looking at in the memory
in order to transition.

And the effect that this
is going to have is that we

are going to be allowed
to suddenly re-read things.

So because we are writing things down,
we can go back and look at them later.

So because we have memory where we can write
things down, we can look at them later.

So a Turing machine is a
finite state automaton where

we have memory that we
can read to and write from.

And we're able to transition to different
states depending on what's in that memory.

So let's take a look at basically what's
going to be happening here.

Inside this Turing machine, we can think
about the Turing machine as a finite state

automaton looking at this semi-infinite
tape.

And what it can do is it can look at one
location on its tape at a time,

make some decision about what state inside
its finite state automaton to transition

to, and then after it
does that, it's allowed

to change the memory
or change its location.

What position in the
memory it is currently

reading from by either
one space left or right.

The way that a Turing machine operates is
it says it's in a state.

It is looking at a cell in memory.

And then using that information,
it makes some decision.

So it uses this in order to make some
decision about what state to go to next.

It makes a decision about what to write at
that location of memory.

And also whether to move left or right in
the memory.

So that's all that a Turing machine is
going to do.

It's going to look at its current state,
what it's currently reading in memory,

and then using that information,
it is going to change to a different

state, possibly overwrite what it was
currently looking at in memory,

and then move either left or right in the
memory.

And the way that we're going to decide
which thing to return is there are going

to be two special states in the Turing
machine.

One state we identify as
an accept state, a return one

state, and one state that we
identify as a return zero state.

So if we're ever in the
return one state, then we just

stop computing altogether
and return one right then.

Just like when you're in Python,
if you execute a return line in your

program, you stop your function and just
return right then.

In our Turing machine, if we ever enter
that accept state, we stop and return one.

If we ever enter the reject state,
we stop and return zero.

So we have these two special states.

Accept means return one.

Reject means return zero.

When we start computing,
we're just going to say

that our memory is sort
of preloaded with the input.

We're going to have a bunch of bits that
are just already on the tape.

We're going to understand those bits to be
the input.

So we're going to reach out.
Programmable tools.

Now, you can make a current note.

And this is the second one.