---
Video Title: Church-Turing Thesis
Description: Theory of Computation
https://uvatoc.github.io/week9

18.1: Church-Turing Thesis

David Evans and Nathan Brunelle
University of Virginia
---

We're going to get to what I think is
probably the single coolest idea,

at least the coolest result in all of
computer science.

Hopefully, you'll see things in a new way
from this that should really get to the

crux of the biggest question
that this course is trying

to answer, which is what
can and cannot be computed.

So we started to get to that last class,
where by just looking at set

cardinalities, we concluded
that there must be some

things that can't be
computed by a Turing machine.

So we said that the Turing machines are
accountable.

We can write them down
as finite binary strings,

but the real numbers
are bigger than that.

The cardinality of the
real numbers is bigger

than the cardinality
of the natural numbers.

So there are some
numbers that And there's

some functions that we
can't compute as well.

But we didn't see if there were any
interesting ones.

Most numbers are not interesting.

And most interesting ones, it seems like,
well, we can't compute them.

And there's actually a section of Turing's
paper that goes through a bunch of

different kinds of numbers and shows that
those are computable to give you a sense

of, yeah, it seems like we can actually do
what we want with this kind of model.

Today we're going to
get to see some specific

examples of functions
that are not computable.

And we'll actually, you know, not just see
some, we'll get to a very strong result

that is basically every
interesting function that we

might want to know about
a program is uncomputable.

Why do we care so much
about what Turing machines can

compute before we actually
get to what they can't compute?

We define this very specific
model, and we're asking

and answering these
questions about a specific model.

And not only that, the actual
model that we talk about

keeps changing because
the book is getting updated.

The real question is, what's so special
about Turing machines?

We could think of lots of different
models.

And what's special about Turing machines
is that our reason for thinking about

these models is that they're actually all
the same.

All models that have any
semblance of what we might think

of as a computer seem to be
equivalent to Turing machines.

So this is actually what's called the
Church-Turing thesis.

It's a name for Alonzo Church who we
haven't talked about much yet.

But around the same time Turing was coming
up with Turing machines, Alonzo Church

came up with lambda calculus, which you've
used at least in Python.

The lambda expression comes from that.

And he answered the same question Turing
was trying to answer with his Turing

machine model about this
question about things that

are decidable that came
from Hilbert's problems.

And he solved that by inventing lambda
calculus and showing that that seems to be

a model of computing that's useful and
there are things that it can't do.

And Turing established this Turing machine
model that we've been talking about.

And it turns out those are equivalent.

And what either one of those models can do
is simulate any mechanical computer.

And that's basically the Church-Turing
thesis to say that this model of

computation is powerful enough to simulate
all other models of computation.

So this is called the thesis.

It's not called the theorem.

So if it was a theorem, that would mean we
should have a proof.

If it was a conjecture, it means,
well, it's something, a proposition

someone has stated, but we haven't been
able to prove yet.

But this is called the thesis.

So why is this a thesis and not a theorem?

Is this something we should be able to
prove if we tried hard enough?

Yeah.

This is really a claim about something
that we haven't defined.

So for any defined computer, well,
then we should be able to have a concrete

proof that says whether
or not this is as powerful as

a Turing machine or more
powerful or something else.

For any concrete model of the computer
that we define, well, then we should be

able to have a proof that says whether
it's equivalent or not.

You'll do lots of problems like that.

But this is stronger than that.

This isn't saying for some specific model.

It's for any model in this large,
vaguely defined class that we can't even

define, but something
that corresponds to our

notion of what we think
a mechanical computer is.

So that is not a defined mathematical
object that we can prove things about.

It's something much more intuitive than
that.

If you read Turing's paper,
which you're not really assigned

to read, but I hope all of
you will read at some point.

Maybe not this week.

He makes this argument.

And it's pretty nice the way he makes it.

So there's computable numbers,
which is this notion, the question of what

numbers can be computed by finite
mechanisms.

Well, that wasn't stated as
what can a Turing machine

or what can some specific
formal model of computing do.

It was stated as things that can be
computed by finite means.

That isn't defined what we can actually
use to compute with.

And so he makes this argument that,
well, we're going to claim that the model

actually covers
everything that we could

reasonably think of as
being done by a computer.

And he makes that three ways.

So he makes an appeal to intuition.

Certainly, that's not a mathematical
proof.

He says for some specific definitions,
we can prove their equivalent.

But that doesn't cover the whole thesis.

That just says these specific things that
seem like they're really different.

And certainly, lambda calculus and Turing
machines seem really different.

We can show their equivalent.

The third thing is, well, we can look at
lots of functions that we think we should

be able to do and show that our model can
do them.

Or in this case, look at lots
of numbers that we think we

should be able to compute
and show that we can do them.

All of those are things that are meant to
build confidence in this intuitive fuzzy

argument that everything that we can
imagine as a mechanical computer can be

simulated this way or is equivalent in
power to this.

But it's not something we can't ever
prove.

Part of this intuitive
argument is also connected

to the simulation
argument for specific things.

So one of the things he argues,
which I think is pretty neat, is...

And we talked about sort of why finite
number of states and saying, well,

maybe human computers can do more than
that.

Maybe they can keep track of something
else.

And he argues that, well, any model that
wouldn't account for maybe the human

computer can leave in the middle of a
problem and go have dinner and come back.

And they better be able to continue where
they left off and not make a mistake or

not lose track of the problem they were
solving.

Any model that can't account for going
away and having a break doesn't seem right.

If we account for the human computer
should be able to take a break,

that means everything that they need to
keep track of to be able to continue has

to be something they can write down in a
finite, simple way.

That's a very intuitive argument.

You could argue that, well, the human
computer shouldn't get to take a break.

And there might be something
they can keep track of in their

head that you couldn't keep
track of with a finite state.

But that's just an intuitive
argument that the things that

we can think of computers
doing, we can model this way.

So what the result of this is,
informal notion of we can simulate any

mechanical computer with a Turing machine,
if we can simulate any other computer with

this one, that means
that this one is at

least as powerful as
anything it can simulate.

So that is making this very strong claim,
which, again, is based on this informal

notion of what mechanical computers are,
that all conceivable computers in the

universe that we know, and probably any
other universe we can imagine,

are no more powerful than a Turing
machine.

So if we can find things
that a Turing machine

cannot compute, that's
a really strong result.

It's not just this specific model can't
compute it.

It's that anything we can imagine as a
computer cannot compute that function.

I talked a few weeks ago about this leaked
quantum supremacy paper.

Now it's no longer leaked.

It's now officially announced.

And there's lots of debate about it.

Does this have any
impact on this question

of whether the
Church-Turing thesis is true?

Apparently, the construction people object
to it.

But no, right?

So none of this debate has anything about
the Church-Turing thesis, right?

All of this could definitely be simulated
by a Turing machine.

So quantum computers are definitely within
the conceivable universe.

There is the extended
Church-Turing thesis that

is about how many steps
you need to simulate.

And this actually raises questions about
that.

But it doesn't raise any
questions about the what problems

can be computed or what
functions can be computed.

Because we can certainly simulate a
quantum computer with enough time,

enough steps, and this is a mathematical
object that's infinite.

So we don't worry about that with a Turing
machine.

So that's why it's such a fundamental
question.

But to answer it, we need a specific
model.

And the specific model is the one that we
defined last class.

Thank you.