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

24.4 Power of Nondeterministic Turing Machines
- Formal definition of Nondeterministic Turing Machine
- Adapting the Execution Model for Nondeterminism
- Power of NDTMs

Nathan Brunelle and David Evans
University of Virginia
---

I'm going to define this a little more
precisely, make sure we understand what

we're talking about when we talk about a
non-deterministic Turing machine.

So this is our definition of a standard
Turing machine from before.

We have a finite number
of states, we have a

finite alphabet, and we
have a transition function.

A transition function takes a state,
an alphabet symbol, and it outputs a new

state, an alphabet symbol, and a
direction.

How is that going to change if we want to
describe non-deterministic Turing machines?

Do I have to change the states at all?

Okay.

Do I have to change the alphabet?

No.

Okay.

So what do I have to do with the
transitions?

If there was one word
I have to change in this

description, what's the
one word I have to change?

It's not a function.

If we can have multiple different
transitions on the same state,

it's not a function.

We could think of it as, well,
now we've got a transition relation.

That we could have a mapping
that the same input in the

domain set now maps to multiple
things in the co-domain set.

Is there an easier way to think about
this?

So we still want to be able to write down
these machines.

So writing down relations is a little bit
painful maybe.

Is there another way you can do it?

We could have a set of functions.

Good.

We could have a set
of functions or we could

have a function where
the output is a set.

I think the most natural
way is to say we can still call

it a function because it's
easier to have functions.

And we're going to say, now we have a set
of these.

So for each possible configuration, we
can output multiple different next steps.

Okay.

So that's all we have to change.

We have to turn that into a set.

Now it's a function again, but it's a
function instead of from the current state

and read symbol to one next thing to a set
of possible next things.

If that set has size one,
if they're all singleton

sets, it's the same as a
deterministic Turing machine.

If that set can have
size bigger than one, now

we've got a non-deterministic
Turing machine.

So that's all we have to change about our
Turing machine definition.

Do we have to change anything else?

Yeah, we need to change our execution
model.

This is just the way we write down a
Turing machine.

So we need a new execution model.

As a reminder, our execution model for a
Turing machine.

It's a lot of text on the slide.

We are starting by initializing the tape,
and then we are repeating each step.

We're looking up in the transition
function.

We're getting the next
state, the symbol to

write on the tape, and
the direction to move.

And we're moving in that direction.

And then if it halts, if we eventually get
to a rule where the directions halt,

then we have an output that we read from
the tape.

What do we have to change if we want to
make it non-deterministic?

There are two ways of thinking about it.

The way that we always make the right
guess is a useful way to think about it.

That's going to be really hard to put into
our execution model.

I don't know any way to define an
execution model that says, if there are

multiple choices, make the right guess,
magically.

If we could do that, we'd be done.

But we'd just say like, well, now this is
a set, but magically pick the right one.

And we'd be done.

But we don't know how to magically pick
the right one.

So what we've got to do is simulate all of
them.

So what does that mean we're going to have
to change?

This isn't going to just be one.

We're going to have to do a loop through
all the possible outputs.

And each time we do one, we're going to
get to some new configuration.

And we're going to have to keep track of
all the configurations.

So we're going to need another loop.

So we're going to go through all of the
possible configurations we could be in now.

For each configuration,
we're going to look up the

rule based on the current
state of that configuration.

The state in the input.

And we're going to get a set of next
steps.

And each of those is going to lead to a
new configuration.

So we're going to have to keep track of
all of those.

Let's assume we can do all that.

Do we have to change anything about rule
four?

When do we decide that we're done?

So any of those possible configurations that
we follow could lead to a halting state.

What should we do?

Yeah.

Let's think about what we did for the
finite state machine.

If our rule was in order to accept all of
the executions we have to accept,

what would the non-deterministic finite
state machine have been?

Yeah.

Well, the only state that would accept
would be the three state.

If we had to accept on all
paths, any time we split, it would

not recognize the strings
that end in zero, one anymore.

I don't think it would accept anything,
at least this particular machine.

If we split on either zero or
one at the beginning, we're

split and one is going to end
up in a non-accepting state.

So at least for this example, if our
definition of you only accept if all

possible executions
accept, it's definitely

different from what
we did from that effect.

That doesn't necessarily mean
there isn't a sensible model,

but it's not the one that's
going to be most natural.

Our accepting is going to be if any one of
those paths halts, we're going to halt.

What should the output be?

We've got a quadrillion different turning
machines that we've simulated.

They all have different things on their
tapes and one of them is halted.

What's the output?

It's whatever's on the one that halted.

And of course, there could be other ones
that eventually halt.

Non-determinism means we don't necessarily
get the same answer.

The way we might
define it formally, we might

define it so we always
get the same answer.

It depends a lot on what these four h's
mean.

If we're thinking of sets that are
unordered and we go through them in any

order, then we're not always getting the
same answer.

We might sometimes halt.

One machine halts before a different one.

We're going to take whichever one halted.

So the one that halts
better give us the output that

we want, because that's
the one we're going to take.

It might be that we could run the same
machine.

Again, a different one would halt first,
and we'd get a different output.

It's non-deterministic.

But if we define our machine well, we
should be happy with any of those answers.

This is an attempt to write that out a
little more formally.

We've got two four h loops.

We're going through all
the configurations, and

we're going through all
the possible transitions.

And each time we do that, for each transition,
we're adding something new to our set.

And we need to do something at the end of
this loop that updates z.

We have to be a little
careful that we don't start

taking steps on the
configuration that we just created.

If we're going to get
the one that halts, we

better do this search
in a breadth-first way.

If we search one path
all the way, it might never

halt, even though there's
some other path that would.

But if we search them all
in a breadth-first way, we're

going to find one that halts
if there is one, eventually.

We have a good sense of what it means to
run a non-deterministic Turing machine.

Is it more powerful than a deterministic
Turing machine?

So are there functions that we can compute
with a non-deterministic Turing machine

that we could not compute with a
deterministic Turing machine?

Is what I have here... does this look kind
of like a reasonable Python program?

Not that reasonable, but you can imagine
turning into a reasonable Python program.

Does that help you answer this question?

Yeah.

So if our definitions are
powerful, it's the one we've

been using, the set of
functions they can compute.

The fact that we can write our execution
model...

So this is one of the
reasons I wrote it this way,

instead of the magically
make the right choice.

If I wrote it with the magically make the
right choice operator, you would

rightfully say this is not
something we can imagine a

regular Turing machine or a
regular Python program doing.

But if we write it as simulate them all
like this, well, certainly we could write

a Turing machine that can do this,
a standard TM that could do this.

If we can simulate a non-deterministic
Turing machine, our model for execution

for any non-deterministic Turing machine
is this.

And we can simulate that with a regular
old-fashioned standard Turing machine,

we can't compute anything that we couldn't
compute before.

All the things that you are very expert on
now about halting problems and Reiss's

theorem, all those things hold
just as well for non-deterministic.

Turing machines as they
do for deterministic ones.

Everything that was uncomputable is still
uncomputable.

What about efficiency?

For our non-deterministic finite state
machine, we said, well, running time is

the same because it's going through the
input once.

But it seemed more efficient because we
could describe solutions in less states,

maybe even exponentially less states,
because we needed to blow up to the power

set of states in our construction that
turned non-deterministic into deterministic.

We're asking this question, is a
non-deterministic Turing machine more

efficient than a deterministic Turing
machine?

What should efficiency mean here?

Is this a meaningful question?

Yeah, so we do have a notion of time.

We've defined notion of running time.

So certainly in terms of size of
description,

size of description, that's a good measure
of efficiency.

And it is definitely much more efficient.

It includes a finite state machine.

So we've already
said that that can be

exponentially smaller by
having non-determinism.

Here we're getting at least that amount of
power.

So it is definitely much more efficient.

The other way of looking at efficiency is,
well, how many steps does the most

efficient machine to solve a problem that
computes that function take?

So running time, less obvious.

For some time classes, it is more
efficient.

If we look at a time
class like, say, 3n

squared, remember, n
is the length of the input.

So this is a standard Turing
machine, functions that a

standard Turing machine can
compute in 3n squared steps.

Is that a proper subset of the
functions a non-deterministic.

Turing machine can
compute in 3n squared steps?

Good question, yeah.

So what does a step mean?

So for our regular Turing machine,
we know what a step is.

For our non-deterministic machine,
what counts as a step?

We've got, for each time through this
loop, we're doing all this stuff.

The best way to think of what a step is,
is now instead of the section of your

model... in the magic
always gets the right choice.

That's one step.

The fact that we can't simulate that
always get the right choice.

If we are counting steps, that's what a
step is.

Another way to think of it is, every
thing that you have to do within this loop.

Every simulated machine taking all the
steps it can... It counts as one step.

You're able to do all of that on one step.

That's a really good question...

Because if every transition here counted
as a step, it's definitely not faster.

It would be doing all the
work to simulate all those

steps just the same as a
regular Turing machine would.

So we've got to be careful what we're
counting as steps.

If we define our time classes really
precisely, it seems like it's more powerful.

But the really important
open question is once

we define our time
classes as generally as P...

So this is a very robust time
class that we said, well, this

is good because all of our
computing models, it doesn't matter.

We can change whether we're talking about
a Python program or a Turing machine.

Class P is going to be the same set of
functions.

We've got a very robust class.

What we want to know is, is the
non-deterministic Turing machine going to

be more powerful than a
standard Turing machine in terms

of can it do problems that
we can't do in polynomial time?

So that's what we will get to next class.