Lecture 03 : Part B

IIT Kanpur July 201
20 followers
1 Video View·Jan 26, 2024
[Music]
[Music]
this is the halting
problem set of those strings which
correspond to a to a touring machine and
input and then this particular touring
machine should halt on that input with
an output
bit
okay so basically recursive problems uh
with an instance is given to
you now can you design a touring
machine that's the question
right so it
captures the question
is there a turing
machine to
test whether m alpha hold
onx
right so this is the question which uh
we are formalizing here by defining the
language hold because the yes strings
are the ones where m alpha holds on X so
if you want to recognize this language
decide this language then you have to
design algorithm to test whether mpha is
actually going to Halt on
X and the problem is that when you are
given a bad input where m alpha doesn't
halt on X what will you do because it's
an infinite Loop so it's in other words
you want to test for infinite
loops and that is uh that looks hard and
in fact we'll prove that it's in
completely interactable there cannot be
a
solution so it's
uh uncomp
computability was shown by Church
which was a very tedious
proof nearly a century back and then
much
simplified by
Turing
so Alan
touring when he defined this touring
machine which we now call touring
machine the problem the proof of halting
problem being uncomputable becomes uh
became very simple as you will see
now so halt
is not computable
proof so suppose it is decidable by a
tuning machine
m0 okay so the
proof uh will go via will go by
contradiction suppose it is computable
and then there is a turing machine m0
which is deciding halt which means after
finitely many steps it can tell you
whether m alpha hals on X or
not see it
outputs
one on Alpha comma
X 1 on Alpha comma X
if m alpha on X
holds
zero if m alpha x doesn't
hold doesn't halt means it goes in an
infinite
Loop okay so so what can we do with
this with this
information so
actually the impressive thing in the
proof is uh once you know that this T
once you have assumed in this case that
m0 exists you can actually feed m0 to
m0 okay that will give you the
proof and that will actually first give
you a contradiction and that will show
that m0 cannot exist so let what happens
when we feed m0 to
m0 so let's do that
formally so Define turing machine M
[Music]
Prime as
follows so given input
Alpha
if m0 on Alpha comma Alpha is
1 then output one okay so what is what
is the behavior of M Prime so M Prime
takes input a string which you should
think of as a description of a touring
machine and you feed
Alpha on the input alpha alpha and Alpha
to m0 as
input
so basically m0 will simulate uh the
turing machine described by Alpha on
Alpha itself right so here we are
actually
sending uh we are trying to M
uh so let's go back to the definition of
m0 so m0 is a turing machine is an
algorithm that decides Hal right so when
will m0 alpha alpha be
one only when in fact effect if and only
if m alpha holds on
Alpha sorry it should be the
opposite that is the beauty of
it doesn't
halt if m0 doesn't halt uh if m alpha
doesn't halt on
Alpha then M Prime
will negate the answer okay it'll output
one what if m alpha holds on Alpha so in
that
case
simulate m alpha on Alpha
computation and
output the negation of what you
get Okay so this completes the
definition of m Prime what M Prime is
doing is it is exploiting
m0 to check whether m alpha is going to
Halt on Alpha or not on itself or not if
it doesn't then it outputs one if it
does then it negates the
answer that's M Prime so what is the
contradiction well we still don't have a
contradiction but we have
uh a touring machine we have defined M
Prime which is doing something
funny and contradiction will come when
you run as I have suggested M Prime on
itself that is where the contradiction
will
happen so let
uh beta now be the encoding of M
Prime during machine M
Prime that is M Prime is M
beta and ask the question uh what is
what will mbaa do on
itself that's the
uh question which will lead to a big
Insight okay what does this steing
machine beta do on itself so beta on
beta
so
if M beta on
beta now remember that
uh
there is no problem in M prime halting
it always halts right no matter what uh
input Alpha
is it always hold so maybe I should
write
that there's no issue about M Prime not
halting on some inputs it always will
halt because it either send outputs it
halts and either outputs zero or one
there is no inite Loop issue in M Prime
so M beta beta can have only two
possibilities either it hals give
you gives you one and it holds gives
you zero that's the only possibility so
what does it mean when it hals and give
you one so then um it means that
uh either U m0 on
beta
beta is
zero but I mean basically it's saying
that either M beta on beta does
not uh
halt which will obviously contradict
that M beta beta is
1
so this is actually coming from step
one they think of this as step one
case that is one place where you can get
output one but that happens only when m0
beta beta is zero which is
uh which gives a
contradiction
can't
halt so that leads to a
contradiction right because we are in
the case where M beta beta value is one
so obviously it halted so it cannot be
that you got output one in Step One
let's go to step
two so
or
uh M beta beta
HS but in step two getting an answer one
output one means
that the value of M beta beta has to be
zero so which again is a contradiction
because we are in the case where M beta
beta is 1 right so so hence M beta beta
cannot be
one that is what we have
deduced so now let's go to the other
case so this means
that M beta beta has to be
zero that's the only case
left in this
case uh output
zero uh in the in in these two steps
when do you get output zero it's only
possible in step
two and uh which means that M beta beta
should be
1
which is also a contradiction because we
have deduced that MB bet is zero right
so so you have to maybe look at this
proof many times before you completely
understand what just
happened so what happened is we assumed
that m0 exist halting problem solution
exists from that we designed this m
Prime which kind of uh negates the
answer and also takes care of the
infinite Loop so that M Prime
is it always
holds and then we are asking what
happens when M Prime is given M Prime
itself right and there we have ruled out
all the cases which means that M Prime
cannot exist which means that m0 cannot
exist it's a prove by
contradiction so this means that M
Prime can't
exist which means that m0 can't
exist right so we had assume that m0
exists so we have now deduced that halt
is uncomputable
right so this is
a this is a first breakthrough in
Insight that once you have formalized
machines then machines cannot understand
machines right right at least machines
cannot even even machines cannot even
decide whether other machines will
stop right
that uh that is an
uncomputable question in that model of
machines and since we believe that
Turing machines are the only possible
machines so Hal just cannot be
computed ever by any
model so this proof technique is
called diagonalization
argument why is
that what is the diagonal
here okay so for to see that draw this
picture
so list your Turing machines m alpha
here uh the rows basically are indexed
by touring machines and the columns are
indexed
by input
X
okay so both obviously rows and columns
are indexed by
strings and
uh now you
ask for this row row
string you fill the
answers on
the column string being used as
input
and what this uh turing machine M Prime
is doing it is negating the answer right
so it's
actually working
here it's negating the answer of what m
alpha alpha on Alpha right so Alpha
comma Alpha is referring to the first
diagonal entry you can think like that
then for the second
[Music]
string
is the second diagonal entry alpha on
Alpha then
third is the third
Alpha uh acting on the third Alpha input
as input and so
on okay so this is the diagonal being
talked
about so this is the
diagonal
so the machine uh m0 that we defined or
M Prime that we Define using
m0 it's actually only looking at the
diagonal uh these values and negating
it so once you negate the diagonal then
you
get um so that is what then leads you to
contradiction because now when uh if M
beta
existed I mean when mbaa you act
on you uh simulate M beta on
beta
um that will give you a
contradiction okay so it was all about
this these diagonal
entries if you have negated all of them
then that gives you the contradiction
there cannot be a turing machine um in
the row
indices right because row indices any
index that you look at it will uh be
unable to give you the right answer so
beta cannot come here for
example M beta cannot exist here right
because when you see its answer here you
will see that it's
negated okay so this is the
diagonalization technique it is actually
not the first time that Turing used
it uh I mean definitely in computation
he was the it was the first time but in
math in other places this idea has had
appeared so let me just write
that a touring machine is
designed
that
disagrees with m alpha alpha for all
Alpha right so that turing machine M
beta cannot exist that was the
contradiction so this technique we'll
see in this course as well which is why
I
have um given you this
recap and uh before this it was used in
other math
results so this technique was
used in other in
earlier
foundational so what were those
foundational
results
so first is and I think this is the very
first where this technique was invented
by caner so Canter's proof of
uh the uncountability of
reals uncountability of
reals okay in
1891 so what is this result this says
that uh the set of real
they are in
bje with subsets of natural
numbers I mean this you already know uh
you can write any real as basically like
looking like a subset of natural numbers
um can just think about
the reals between 0 to one so they are
in decimal representation you can think
of the binary string appearing after the
decimal point and that is a subset of
that defines a subset of natural numbers
by their positions of
one
uh and what caner showed is the
following that this
is strictly bigger
than the set of natural numbers there is
no bijection okay so there is a there
cannot be a bijection between natural
numbers and the set of natural numbers
the set of sets of natural numbers or
set of subsets of natural
numbers so reals is strictly bigger
than natural
numbers in fact you can also put
rationals
here and because rationals are in
bijection with natural
numbers okay so reals are strictly
bigger
than rationals though obviously both are
infinite sets so caner was the first one
who actually can compare uh two
Infinities okay by his his argument so
maybe try to prove this uh by the
diagonalization
trick as the homework
exercise second is uh Russell's
paradox
slightly
later so Russell's Paradox sh says that
certain sets don't
exist okay so you for example you cannot
say Define let a be a set that
contains
everything okay so such
definitions he showed they don't make
sense and the way he showed it is by
showing that the Set
uh Y which contains X's says that X is
not contained in
X this doesn't
exist
okay so this also you can do so you can
prove it using the dation trick as an
exercise so although I have written the
definition here but this definition
actually doesn't make
sense which is uh the
Paradox third is
uh probably the most famous One
gel's incompleteness
theorem which came much
later around the same time as Turing
actually so incompleteness theorems
theorem says that
uh there are actually statements in math
which you can cannot prove or
disprove it's just impossible so there
exist unprovable
statements okay so unprovable means that
uh you can write down or goodle wrote
down a statement which
uh you cannot prove it's true you cannot
prove it's
false
either true or false cannot be
decided so their truth
is
undecidable okay and This Ti is actually
very well with also halting
problem um yeah so some of
the mean really
big
uh big steps in
math also philosophically speaking they
actually involved the diagonalization
argument okay so so enough of this so
now we move on to more complexity
things only looking at problems that are
computable so for
that let me Define the notion of
reduction how to compare problems that
are
computable
um let's
say in an equal
way so a
function
if can be shown
uncomputable okay we are still in this
possibly uncomp computability regime so
okay how can you show other functions to
be uncomputable or other problems to be
uncomputable that you can do if you can
you will get that if you can reduce
halting problem to your problem right so
that because once you have a reduction
obviously your problem cannot be
um uh easy because if if if it was easy
then you will also solve halting problem
so your problem is also hard that's the
idea of
reduction so a function can be shown
uncomputable
by reducing it to
by
reducing so notice the direction by
[Music]
reducing
halt to F okay that's the correct
direction that would mean that f is also
uncomputable it's very
hard so that is uh
design
a
computable function f Prime such that
for all
inputs Hal on X is the same as so what
will fime do FR Prime will basically
modify the input
X and then apply
f
okay so reduction is nothing but a
composition okay by where a computable
function is involved that you have to
design so this F Prime is the key
thing this you have to design this is
called a
reduction so B will basically when you
actually wanted to solve
halt on x so instead you modify uh X and
give it to
F and that will solve Hal okay so this
third function this is called reduction
if this exists then it shows that your
problem is
harder and uh we write this
as
halt reduces to
F Turing
reduces okay there is a turing
reduction and this means that f is also
uncomputable so we'll make it more
precise for uh complexity in the next
[Music]
[Music]
[Music]
class
[Music]
