Lecture 03 : Part A

IIT Kanpur July 201
20 followers
Jan 26, 2024
[Music]
[Music]
so we were doing uh
asymptotics right we have
defined bigo big Omega Theta small o
small Omega o Tilda and Omega Tilda
so this Omega TAA was big
Omega big Omega Tilda and similarly you
can also Define small o Tilda
and uh small Omega
Tilda so points here or maybe we do some
small examples
first
so if you look at the
function n plus n n Square * 100 okay n
is the formal variable think of it as
input size so if you have a algorithm
that has this much time so this we can
write
as bigo of n Square simply right because
100 is a constant Factor we can drop
it and then in n and n Square n Square
dominates so you can actually say that
the whole thing is kind of n Square so
that is what bigu of n s
signifies but we can also say that this
is
actually big Omega n
s right because it is not
only upper bounded by a multiple of n
Square it's also lower bounded by a
multiple of n Square so ultimately it's
actually Theta n²
it's all
three and uh it's
also uh small
o let's say of n to the
2.01 right because uh n+ n² will be
smaller
than uh n to 2
point something so you can put 01
01
.1 so LHS left hand side will be
strictly smaller than this right in the
limit limit of the ratio is zero on the
other hand it is strictly bigger
than n s by
login right n s by login is strictly
smaller than n Square so n + n 100 100 *
n + n square is actually strictly bigger
than this okay another example is
uh which you will often see and
login so what is n login n login is uh
upper bounded
by let's say this power into to the
1.01 right and login is is almost a
linear function so
anything uh n to the 1 plus Epsilon
that will be
larger and in fact it is small o of n to
the 1+
Epsilon for
any positive real number
Epsilon in the limit because login by n
to the Epsilon tends to zero that's
important to remember so log n is
exponentially smaller than
uh any polinomial in
N so in general you should remember
that n to the C is always smaller
than 2 to
n for all constant
C
okay polinomial is always smaller than
exponential this is what we are saying
here this asymptotics uh you should
always remember this is important okay
some more
remarks so the as mentioned before the
input output
tape is only only for writing the output
string okay you are not allowed to do
anything else on the io
tape um for all the other stuff use the
work
tape
and sometimes you may not even need to
write the output you can also just place
it on the work tape if it is small
enough especially if it's a decision
problem okay a
second important remark is that uh in
know you know this B inary search
algorithm
right so is binary search really uh
login time so in terms of turing machine
it cannot be so you can
search a name in a
directory
in login
steps in
fact quote unquote login
steps but
uh this is actually not possible on the
on the tape right because on the tape uh
your head can only move once cell at a
time one cell to the neighboring one of
the neighboring cells so it cannot
really jump from uh one end to the
midpoint of the input okay that jump is
not possible so that jump will actually
already take n by two
steps so uh so this login step algorithm
which you keep seeing in binary search
this is
actually uh not in the Turing model okay
there you assume random
access and turing machine does not have
Random
Access so it doesn't
mean uh login
time okay this this is uh not the time
complexity in terms of touring
machine why
because you need to
assume uh
indexing and random
access
which
requires n to be fixed or
constant okay so this actually works in
directories well because directories are
finite
uh lens strings right directory will
only have names and names are finite
uh directories cannot be infinite really
so that is why saying login there makes
sense but uh and also you have to jump
you have to jump from end points to the
midpoint and so on
recursively uh neither of those things
are possible in touring machine in
touring machine it will really be end
steps order end steps going from end
point to midpoint moreover um
indexing is not possible I mean you
cannot just number the cells and say
that I directly jump to
CI okay so those things actually are
only possible when n is
constant and N is not constant in during
machine this input size is assumed to be
arbitrary at least when you when we talk
about time
complexity okay so this might be
a common confusion when you compare here
when you try to do binary search in the
Turing model so if you in any algorithm
where you need to look at
uh a long
input you will have to scan scan it it
will be at least linear
time so once you once we have gone
through the definition of turing machine
a definition of problems turing machine
time complexity
astics now we can talk
about
uh what can be simulated on a touring
machine so the church teing thesis comes
into the
picture and what does it say so it says
that everything can be simulated on a
touring machine
so every
realizable Computing
device okay so it could
be transistor
based in the old days or now silicon
based
or in the
future DNA based or neuron
based like our neuron
cells or in the future Quantum
based or any even for now alien
technology
everything can be simulated
by or simulated on touring
machine okay this is the thesis
obviously you cannot prove it you can
only disprove it and to date in the last
one century it has never been
disproved okay so whatever Computing
device Dev is
invented uh or thought
of they are all simul on a touring
machine okay so in this sense touring
machine is is the universal
machine can simulate anything so the
problems which touring machine
solves they are called
what
they are called
computable
decidable or
recursive okay these terms mean the same
thing uh and uh so a problem is
computable if it can be solved on a
tuning machine by an
algorithm uh and a problem is decidable
or a problem is
recursive if there is a touring machine
for it now there is another term which
is uh slightly which is more General
than recursive it's recursively
innumerable
so recursively inumerable is a more
General
concept okay just I wanted to note
that that innumerable when we say it's a
different
term so recursively there are recursive
inumerable problems which may not be
recursive which may not have a touring
machine an
algorithm okay so innumerable just means
that there is a touring machine which
can output the yes strings like keep
printing the yes strings in some order
all the yes strings will be printed
okay uh but
uh
that uh somehow is not not the same
thing as computability
in computability you will be given an
the turing machine will be given an
input and then the turing machine has to
Halt and say Yes or No Yes string or no
string so I'll not go into this because
this is already covered in theory of
computation a
lot but
uh yeah the most General thing you can
think of is uh recursively inumerable
and recursive is um more special and
what is more special if which we study
in this course for
is efficiently solvable
problems okay so what are
they
so function f we will call polinomial
time
computable
okay polinomial time computable not just
computable but computable how fast so
polinomial time that's the time
complexity and obviously you can Define
it as if there exists steering machine
M for
f with time
complexity
with time complexity
TN and TN has to
be a poly function polinomial in N so n
to the
C okay where C is an absolute
constant
what does constant term means constant
means uh doesn't depend on n on the
input size okay so that is independent
of of the input size n this is what we
will always mean
okay
constant uh variable will be n input
size because you want to study all the
all possible inputs and constant will be
something that doesn't change with
n okay so C is a constant it's a
actually a universal constant think of C
as
10 and the functions which uh have a
turing machine that holds in in this
much time and to the C
time at
most those
functions those problems are called
polinomial time computable so we'll
usually shorten it to poly
time and uh in formally we can call
these Turing machines efficient
algorithms so
informally
we call such
F or maybe we
call such touring
machines or
algorithms um efficient
algorithms
okay so almost always efficiency or
efficient algorithm will
mean uh Turing machines with time
complexity a polinomial even if it is n
to the
100 we are calling it efficient because
as remarked before n to the 100 is
smaller than 2 ra to
n okay so 2 ra to n we call inefficient
and N ra to C we call
efficient so let
me give you an
exercise so any c
program okay okay you write if you are
looking at a c program that is efficient
its time complexity is polinomial in the
input size any efficient C program can
be
written as an efficient touring
machine
and
conversely any efficient uh turing
machine or algorithm can be converted
into a c
program efficient C
program okay so just do this simple U
exercise just to so that you understand
the relationship between uh actual C
programs and these abstract touring
machines or mathematical touring
machines the I mean the reason why this
efficiency translates is uh or captured
by turing machine is is
uh obviously during machine
steps each step is so simple you can
simulate it by a c
program and so if the steps are few in
teing machines steps will be few in C
program
execution for any computer program
execution um Converse is true because
whatever C program will do or a computer
program will do during execution on an
input
uh it can be
Faithfully uh simulated by turing
machine
steps so the turing machine will also
have few steps okay just convince
yourself about about
this so what this means is uh this is
kind of
um kind of an efficient version or
variant of church during thesis if you
will that all these realistic
computations which are
fast they are fast because the touring
machine implementations are also fast
so so
thus if a
problem is hard for Turing
machines then it is also hard in real
life right so that is why Turing
machines are so popular amongst uh uh
theoreticians
because if we show that some problem is
very hard for turing machine then it
must be very hard also for it will be
very hard also
for any kind of realistic
computation uh now notice that chur
steing thesis was a bit more General it
didn't talk about efficiency only talked
about
computability
so
um that has held
true uh efficiency part in the future it
may change because for example it is
known that if you can design quantum
computers then they can solve problems
faster
than existing
computers Okay
so
so let me just remark
that this efficient if you
will Church during
thesis might
fail or yeah it will
fail
if if you build a quantum
computer this is
known okay we'll not do it in this
course but you can do it in Quantum
computation uh courses
okay so this is why this uh there is a
problem in F efficient version of church
during
thesis that uh it may not be true that
any efficient problem can be solved on
real computers there might be some other
archit some other architectures or
physical devices which may solve a
problem faster okay for example quantum
computers could possibly solve
um let me call this
m so certain problems uh we believe are
solvable faster on quantum computers
than current
computers
but remember the this is we are only
comparing efficiency computability is
trivial okay computable the problem
whether you solve it in this much time
or much bigger time uh
computability is not concerned about
that computability is only concerned
about finite
time right so that churching thesis
stands solid but efficient version is
not uh so powerful or so
realistic so
can you feed a touring machine to
another touring machine as input okay
which is like saying uh can you can a c
program take another C program as input
so of course yes because compilers do
that all the time compilers
St as input right so let's do that
here so feed curing
machines to
themselves
so how do we formalize
that it's not uh
difficult because touring machine
remember has finite
control so it's a finite string you give
that to another turing machine as input
so turing machine has a finite
description
right alphabet
State transition function or think of
the state diagram it's a completely
finite uh I mean by definition it is
finite so you can think of giving that
picture to a touring machine
right
so we can encode it
as a Boolean
string okay so there might be many ways
to encode let us fix one so let us fix
some
encoding
so for example one option
is first the gamma is presented in
binary then comma is put and then Q is
presented in binary and then Delta is
then comma is put and then the
transition function Delta is put in
binary right so that's a string and that
represents a touring machine and you can
give this to your algorithm or your
touring machine okay so touring machine
taking a touring machine that is
possible and for
uh a string
Alpha we can
write
m
alpha to be the turing machine that
string Alpha represents now since the
encoding is fixed in some way maybe not
every string is a is a is a turing
machine is describing a touring machine
so if it doesn't then you in that case
you
take the turing machine m alpha
uh to be just some trivial touring
machine
so okay so let me Define it in two ways
so mlpa is the turing
machine that Alpha
encodes if Alpha does
encode
otherwise the turing
machine Computing the zero
function if
Alpha doesn't incode
okay so this is a definition by two
cases so either Alpha does encode a
touring
machine then you just use that touring
machine as m alpha M sub Alpha if Alpha
doesn't encode a touring machine then
you take the zero touring
machine
so so yeah now strings correspond to
Turing machines and that is amazing
right that any string can be seen as an
algorithm so every string is also an
algorithm right so you can think of
strings as algorithms algorithms as
strings if you think about it when you
write a c program it is already a string
right it's a string in your English
language for
example so just so so just that idea but
abstracting it mathematically will be
very helpful
so
now you can
uh
see
that there
exists a
universal turing
machine U that on input alpha
x uh
simulates
m alpha on
X okay so now you can design a touring
machine called
U which will take a another turing
machine with its input and then run that
turing machine on the given
input and either halt given an answer or
doesn't
halt all that depends on what Alpha was
right so what is the steering machine
design
so this again is uh you can do it as a
homework
exercise so
youu let me just say it's a proof idea
not the formal
proof formal proof you can write
down so you
reads the transition
function
Delta of m
alpha and decides the next
step and remember that U also has two
tapes input tape on which Alpha comma X
is written and there is a work tape so
it can actually divide its own work tape
into I mean you can
use to
simulate tapes
for m alpha right so the only thing
which is missing in Alpha are these
tapes which m alpha would have had they
are missing because Alpha is just a
finite string there is no infinite
memory there but memory U has U has two
tapes in fact it has this work tape so
on the work tape it can simulate
whatever m alpha wants to
do right it can in fact in the worst
case it can divide its own uh you can
divide its own work tape into an input
part and work tape part and whatever m
alpha says it can simulate
that
so so do
that as complete this proof as homework
sise see whether what the time
complexity of U
is is it is it as good as m alpha is it
much
worse and
um just with this definition and this
observation now you can show that
halting
problem is terribly
hard so this problem
is the following language halt
right
let me use
Capital too confusion so halt is the
language consisting of strings which are
Turing
machines uh with
inputs so mlha HS on
X and outputs a bit
okay so these are the as halt suggests
name suggests these are touring machines
with inputs on which they Halt and give
an
[Music]
answer
[Music]
[Music]
