---
Video Title: Universal Machines
Description: Theory of Computation
https://uvatoc.github.io/week9

18.3: Universal Machines
- What do we need to simulate a Turing Machine?
- Universal Machines
- Dori-Mic and the Universal Machine! (https://dori-mic.org/)
- A 2-state, 3-symbol Universal Turing Machine

David Evans and Nathan Brunelle
University of Virginia
---

We've seen universal circuits already.

So you should be ready for this.

We saw that we can design a circuit that
takes as input a sequence of bits that

describes another circuit up to a certain
size.

Because with a circuit, we have a limited
size that we can take as our input.

And it can do whatever
that circuit would have

done on that input for
any circuit up to that size.

So it's a universal circuit that takes a
description of the circuit in.

And we saw we could implement a val.

A val is also a universal function.

It takes a description of a function,
in this case in the NAND CIRC language,

still a finite function, and for any
function up to that size.

And in this case, the size is just given
by the size of the input.

It can simulate that function.

We've seen universality in finite
computation already.

What universality means for Turing
machines is exactly the same thing.

But now it's even more powerful because
it's not limited to finite inputs.

I should say, the inputs are always
finite.

I misspoke there.

Inputs are always finite.

We always need to write down our inputs.

Where this is not finite computation is
that we can have the same machine that can

work on any size input, which was not
something we could do with circuits.

What a universal
Turing machine should do

is take as input a
description of a machine.

And we already invented this function that
says, well, either that description is a

valid machine, and that's
the machine it describes,

or it's invalid and we
use the reject machine.

And it takes an input, and it outputs the
result of running the machine that that

input describes, that the W input
describes on X, for any possible machine.

So if we have a universal Turing machine,
we can simulate every machine because we

can describe every machine with a string
of bits.

So we could even simplify this because we
said, well, we don't need input anymore,

separately, because we can make the
machine write out its own input.

So we could think of it just taking one
input, which is the description of the

machine, and output the result of running
that machine.

Can we build it?

So what do we need to do to simulate a
Turing machine?

Okay.

Yeah.

Okay.

Good.
Yeah.

So we need a way to take a step.

So we have, in our description of the
machine, we need to be able to take a step.

So that means we've got our transition
function.

It takes in a state and a tape symbol.

And we need to be able to do something
that can look up.

We're going to have to look up the right
rule in our transition function.

And then we're going to have to update the
state.

Very similar to what
we did for eval, but now

we're doing it for our
Turing machine model.

So we've got to also update what's on the
tape.

We're going to have
to simulate both the

state of mind, which
is really just a number.

That's just the number of the state in a
finite state machine.

And we've got to simulate the tape.

So we're going to have to write to some
location on the tape.

So we've got to have memory.

We've got to have some way to, based on
what's in the table, do different things.

We have to have some way to make
decisions.

We have to be able to, based on,
say, if the rule said, move left,

we have to update the state in one way.

If the rule said, move right, we've got to
update the state in another way.

So we have to have some way to make
decisions.

We've seen we can do if with simple terms.

Definitely anything that we saw we could
already do with circuits, we're definitely

going to be able to build a Turing machine
that can do that.

Is this enough?

Do we just need to be able to model the
memory and be able to make decisions?

Most importantly, how
is this different from.

Boolean circuits or
our NanCirc language?

Those are all straight line.

We always knew when
we ran a val, we had a

list of instructions and
we went down them.

Each instruction was some NAND with two
variable inputs and one variable output.

What do we need to do differently if we're
going to simulate a Turing machine?

It's definitely not going to work with
straight line code.

If we had simulated it
with straight line code,

well, it would not be able
to work on any size input.

It would run for some fixed number of
steps and be done.

So we need some way to make it so we can
keep going.

We need some way to say we're not just
going to do straight line operations.

We need some way to jump back.

Some way to keep going.

Lots of different ways we could think
about doing that.

But once we have those three things,
if we can simulate memory, if we can make

decisions, well, we need enough to do a
lookup table.

But we've seen we can do that with a
circuit.

Definitely anything that we've already
seen that we can do in a circuit to build

a universal circuit, we're going to be
able to do with a Turing machine.

But we also need to be able to simulate
memory that's potentially unbounded,

unlike the variables in NANSERC where it
was a fixed size memory.

Those are the things that we need.

We just need a way to remember.

We need a way to make decisions.

And we need a way to keep going.

These pictures are from my children's book
on universal computers.

I have books to give away.

Once you've got those, you can build a
universal machine.

And you can compute anything you can
imagine.

And this is what Turing did.

So I've been very informed with saying,
oh, once we can make decisions,

once we have memory, once
we can do these things, we can

compute anything, we can
simulate any Turing machine.

That wasn't good enough.

Definitely, if you wanted to
make a really strong argument

about this, you had to show
exactly how to build one.

And this is what Turing did.

Section six of the paper is, I'm going to
build a machine with a fancy U that starts

with a tape, written the description of
some other machine.

This is what we've been calling W,
the description of a machine.

And what it does is compute the same
sequence as that machine that W described.

That's what he does.

In the paper, there's the full rules
saying, here's how to do it.

Rules that you can describe as Turing
machine rules.

We're not going to go through all of them.

You can definitely read them in the paper.

These are the weird German letters that
make it harder to read than it should be.

And it has a compact notation for
describing the rules.

But all the rules are
just based on the simple

kinds of Turing machine
rules that we've used.

And once you have a universal machine,
then you can simulate any Turing machine.

You don't need anything
nearly as complicated

as the one Turing came
up with in the paper.

There's actually a
two-state, three-symbol.

Turing machine, which
arguably is universal.

This seems pretty weird to say that's
universal because it looks really simple.

And this is something
that Steven Wolfram... I'll

refrain from saying anything
about Steven Wolfram.

He proposed this, but he couldn't prove
that it was universal.

He had this machine and this model of
using it.

It's a little different from
the way we've described.

Turing machines, but really
essentially the same thing.

But left it as an open
question with a challenge to

see if someone could
prove that it was universal.

And an undergraduate student in England
was able to prove this.

This is not really a practical universal
machine.

Well, Turing machines in general are not
supposed to be practical.

There's a 40-page proof, and if you
actually wanted to do a computation like 2

plus 2 with this universal machine,
you'd be working on it for years.

I don't know if you could finish 2 plus 2,
but I wouldn't try it.

The basic idea and
why it's kind of still a little

bit fuzzy to say, is this
really a universal machine?

The input to this is not
a description of a Turing

machine in rules like the
way we've been describing it.

The input to this is some very complicated
kind of input that you've basically said,

you start with something that's
understandable that can simulate any.

Turing machine, and then you have all
these translators that translate the input

into some other much larger, much
stranger, much less understandable form.

But each one of those is some simulator
that then you argue none of those

simulators by themselves is a universal
machine, that they all have some limit on

what they can do, but what you end up with
at the end is a universal machine.

So if any one of these simulators that you
ran to produce the input to this machine

was itself a universal machine,
then this would be totally bogus.

It would be saying, well, outside of your
machine, run a universal machine,

produce the output, and then replicate
that.

By showing that none of
these were universal, they

could make an argument
that this is a universal machine.

So these exist.

We can build universal machines.

There are lots of them, even ones with
very few states.