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

17.3: Turing Machine Variations
- No Input Machine
- Two-Sided Infinite Tape Machine

David Evans and Nathan Brunelle
University of Virginia
---

The input was kind of complicated.

We had to start by putting the input on
the tape.

It raised questions about, well,
now we don't necessarily know without

looking at both the
size of the input and the

number of steps where
the last non-blank was.

So let's get rid of the input.

Let's just say the tape starts as all
blank.

There's no input.

Are we happy with this?

Does it make sense to have a computing
model that has no input?

Certainly our Boolean circuits didn't make
a lot of sense if we got rid of the input.

Can we get the input back if we need it?

Or can we do something to make this
equivalent?

Let's assume we had our old model,
where we have a Turing machine and an

input X, and now we want to execute in the
simpler no-input model.

Can we produce a new Turing machine that
doesn't take any input, but will produce

the same output as the original machine
would have running on input X?

So now this machine is going to start with
a blank tape, and it should produce the

same output as the
original machine would have,

starting on a tape
that had input X on it.

Can we define this machine?

Yeah.

Exactly.

Yeah, right?

All we have to do...

We've got to have a machine.

This is going to be our M prime.

It's going to have a transition function
that says in state 0, we're going to read

a blank, and we're
going to write the first

input, and we're going
to move to the right.

And we're going to go to state 1.

In state 1, we're going to read a blank.

We're going to write the next input,
and we're going to move right, and so on.

So we're going to have a bunch of states.

How many are we going to need to write the
whole input?

Yeah, n of them, if it was length n input,
right?

We're going to have n states that's going
to write the last one.

And what do we do after state n?

Because now we've got to get back to the
beginning of the tape.

Yeah, what should we do?

Sure.

We could have n more states that all go
left.

We could have one
state that goes left and

keeps going left until
it finds the triangle.

We want to do something
where we're going to have

a state sort of that's
going to keep moving left.

It's going to not change what's on the
tape, so it can read anything.

It's going to write the same thing back and
move left until it gets to the triangle.

And when it reads the triangle,
it's going to leave the triangle.

It's going to stay.

And then it's going to move to the first
state of the old machine.

And we have no transitions back from the
old machine to the new machine.

We're done, right?

We've constructed a machine that now
writes the original input, rewinds back to

the beginning of the tape, and now starts
the old machine.

So we can always do that.

We don't need input.

We can always incorporate writing the
input into our machine.

The other thing we're going to change,
and all of these changes are things that

we will see later, we're
not going to see today,

don't really change the
computing power at all.

The description we started with said the
tape was semi-infinite, meaning it was

only infinite in one direction,
and it had an end in the left direction.

If we think of modeling the
scratch paper that the human

computers are using, it's
easier to think of semi-infinite.

You don't have infinite in both
directions.

But we can model infinite in both
directions.

So what do we have to change?

Okay.

Yeah.

Good.

Yeah.

All we got to do, instead of using the max
here, it actually simplifies things, right?

The max was there to say we can't go past
zero.

So now we're still going to start at zero,
but we can go left or right.

This is I equals zero.

We can go left as far as we want.

We can go right as far as we want.

Do we have to change anything else?

Good.

Yeah.

We might want to change the output,
right?

We might want to say we shouldn't ignore
everything to the left of zero.

We're going to make the
output everything that's on the

tape between the furthest
blanks in both directions.

We could decide let's
ignore the left side of the

tape, but I think it makes
more sense to include it.

So we're going to have to change that as
well.

So here's how we change it.

We're going to have two sides and we're
going to capture everything between them.

We're going to paradigme.
We've got one small part in one place to
frame our face.
Four.

Four.

Two.

One.