00:00:05
hello everyone welcome to the first
00:00:07
lecture in the course theory of
00:00:09
computation in this lecture I will be
00:00:11
giving you an introduction to the course
00:00:13
theory of computation where we shall see
00:00:16
what this course is all about what can
00:00:19
we study from this course and what this
00:00:22
course has to offer all right so let's
00:00:24
get started so what is theory of
00:00:28
computation this theory of comput ation
00:00:30
is one of the most fundamental courses
00:00:32
of computer science this course is one
00:00:34
of the most fundamental as well as
00:00:36
abstract courses of computer science
00:00:39
which every computer scientist and
00:00:40
Engineers must
00:00:42
know this course is not going to help
00:00:44
you write programs or build a computer
00:00:46
as such but it will help you understand
00:00:50
how people have thought about computer
00:00:52
science as a science in the past 50
00:00:55
years okay so what does this mean and
00:00:58
what is it really about
00:01:00
so this subject is mainly about what
00:01:03
kind of things can you really compute
00:01:05
mechanically how fast can you do it and
00:01:08
how much space does it take to do
00:01:10
so okay so we know that in computer
00:01:13
science there are certain kind of
00:01:15
problems that a computer or a machine
00:01:17
can solve and also there are certain
00:01:19
kind of problems or things that a
00:01:21
machine cannot do or certain kind of
00:01:24
things that a computer cannot solve so
00:01:26
we shall be seeing all these kind of
00:01:28
things in this subject okay so we talked
00:01:30
about how fast and how much space does
00:01:33
it take to do so so let us just leave
00:01:35
these two points for a while and let us
00:01:38
just focus on about what kind of things
00:01:40
can you really compute
00:01:42
mechanically so to make this point clear
00:01:45
let us take a simple example so let's
00:01:48
say I want to design a machine that
00:01:51
accepts all binary strings that end in
00:01:54
zero I want to design a machine that
00:01:58
accepts all
00:02:02
binary
00:02:05
strings that end in zero so my machine
00:02:11
that I designed should accept all binary
00:02:13
strings that end in zero and should
00:02:16
reject all other strings that does not
00:02:18
end in zero okay so let me take an
00:02:20
example string here let's say 11 1 0 1 0
00:02:24
1 1 0 so this is my example string that
00:02:27
I have
00:02:28
here okay now now what I want to do is I
00:02:33
should check whether this string is
00:02:34
accepted by my machine so as a human
00:02:37
being how would I perform this task as a
00:02:40
human being I would just look at the
00:02:41
last digit and if I see that it is zero
00:02:43
I say yes I accept it or if I find that
00:02:46
it is equal to one I say no I reject it
00:02:49
so how would a machine do this a machine
00:02:51
would scan the last digit and if it
00:02:55
finds that it is equal to Zer it says
00:02:59
yes it is accepted
00:03:00
or if it finds that it is equal to one
00:03:02
it says no and it rejects it why because
00:03:05
our machine is supposed to accept all
00:03:08
binary strings that end in
00:03:11
zero okay so that was fairly a very
00:03:14
simple example now let us take another
00:03:17
example in this example I want to design
00:03:20
a machine that accepts all valid Java
00:03:25
code it
00:03:27
accepts all
00:03:33
valid Java
00:03:37
codes okay so what should my machine do
00:03:40
my machine should check the binary
00:03:43
equivalent of my codes when I write a
00:03:46
code in Java it should check the binary
00:03:50
equivalent of this codes and from this
00:03:52
binary equivalent it should tell whether
00:03:55
this came from
00:03:57
a valid piece of java code or it is
00:04:02
invalid okay so my question is is it
00:04:05
possible to design this kind of a
00:04:07
system the answer to this is absolutely
00:04:10
yes we can and the best example I can
00:04:13
give for this
00:04:14
is
00:04:18
compilers when we write a piece of code
00:04:20
into our compilers let's say that I'm
00:04:22
writing a piece of java code so I write
00:04:25
a piece of java code into my compiler
00:04:27
and when I compile that program if if I
00:04:29
have written that program correctly
00:04:31
without any mistakes the compiler
00:04:33
compiles that program and runs it
00:04:35
because it is valid on the other hand if
00:04:40
you have made some mistakes in that code
00:04:42
or if you have written something wrongly
00:04:45
then the compiler tells you that there
00:04:46
is an error and it does not run the
00:04:48
program because it is
00:04:51
invalid all right so we can we see that
00:04:54
it is very much possible to design this
00:04:56
kind of a system and from this example I
00:04:59
I think we got a slight hint that the
00:05:02
whole of compiler design it came from
00:05:04
this subject theory of
00:05:07
computation okay so I hope that was
00:05:09
clear now let's take another example now
00:05:14
in this example I want to design another
00:05:17
system
00:05:18
that that
00:05:21
accepts
00:05:23
all
00:05:26
valid Java
00:05:28
codes
00:05:33
and never
00:05:36
goes
00:05:39
into
00:05:42
Infinite loop I assume you know what is
00:05:45
the meaning of infinite Loop okay
00:05:49
so I want a machine that accepts all
00:05:52
valid Java codes and do not go into
00:05:54
Infinite Loop so is it possible to
00:05:57
design this kind of a system so from
00:05:59
this uh previous example we have found
00:06:01
that it is possible to design a system
00:06:03
that accepts all valid Java codes this
00:06:06
part is possible it's fine but we have
00:06:08
one more condition here and never goes
00:06:10
into Infinite Loop can I design a system
00:06:14
that never allows my code to go into an
00:06:16
infinite
00:06:17
Loop the answer to this is no I can
00:06:21
never design a system that
00:06:23
performs this
00:06:26
task okay so even if you design it you
00:06:29
would either get the wrong output or it
00:06:32
could run forever and give you no output
00:06:34
at all so this kind of a machine that
00:06:38
performs this kind of a task cannot be
00:06:41
designed okay so this third example has
00:06:45
given us an idea about what kind of
00:06:47
things can we not compute
00:06:51
mechanically okay I hope that was
00:06:53
clear so what is this subject all about
00:06:57
this Sub in this subject what we usually
00:07:00
do is that we have a we have a system or
00:07:04
a machine we design a machine and
00:07:06
suppose this is a machine and then we
00:07:09
send an input to this machine and then
00:07:12
the machine thinks about this input
00:07:14
based on some formula or based on some
00:07:17
rules and it either says yes and it
00:07:20
accepts the input or it rejects the
00:07:22
input so this is what we are going to
00:07:25
basically do in this subject we are
00:07:28
going to design systems or machines
00:07:32
which can take certain kind of inputs
00:07:33
and this machine will be based on some
00:07:35
rules and it should either accept the
00:07:38
input or reject the input so this will
00:07:40
be the thing that we'll be doing don't
00:07:42
worry even if it is a little unclear
00:07:44
right now when we take uh other examples
00:07:46
and when we start from the very Basics
00:07:48
from the following lectures it will all
00:07:50
become very
00:07:51
clear okay now now let us see what are
00:07:55
the layers or the levels in this subject
00:07:57
that we have to go through for that I
00:08:00
will show you a diagram over here so
00:08:03
here I have a small diagram showing the
00:08:06
layers or levels in this subject so in
00:08:09
the first layer we have
00:08:12
FSM so what is
00:08:15
FSM FSM stands for finite State
00:08:20
machine FSM stands
00:08:24
for
00:08:27
finite state
00:08:31
machine this FSM that is finite State
00:08:34
machine it is one of the simplest model
00:08:38
of computation it is the simplest model
00:08:41
of computation and it has a very very
00:08:44
limited amount of memory and it can
00:08:47
perform very lowlevel computations and
00:08:50
calculations okay this is the basic
00:08:53
building block of this subject this is
00:08:54
the first thing that we will be learning
00:08:56
so keep in mind FSM it will be starting
00:08:59
starting with it in the following
00:09:00
lectures from the very Basics so don't
00:09:02
worry even if you don't understand these
00:09:03
terms now we will make make it clear as
00:09:06
we go further and then the next layer we
00:09:09
have is
00:09:11
CFL CFL CFL stands
00:09:15
for
00:09:17
context
00:09:20
free
00:09:22
language context free language CFL
00:09:25
stands for context free language and CFL
00:09:29
is a little more powerful than FSM and
00:09:33
it can perform some more higher level of
00:09:36
computations as compared to finite State
00:09:38
machines okay uh and one thing to
00:09:41
remember here this language over here
00:09:44
this language here does not mean a
00:09:45
programming language okay when we in
00:09:48
computer science when we come across the
00:09:50
term language we often think oh this
00:09:52
means a programming language but no in
00:09:54
this subject here in this context free
00:09:57
language this language actually mean
00:09:59
means
00:10:00
a set of
00:10:04
strings a set of strings is what is
00:10:06
known as language it'll become clear
00:10:08
when we uh explain it further in the
00:10:10
following lectures so don't worry about
00:10:11
it and in the next layer we have
00:10:14
something known as touring machine
00:10:16
touring machine is a uh machine that can
00:10:19
perform high level computations and
00:10:21
calculations it was designed by alen
00:10:23
touring in 1940 and it is much much more
00:10:26
powerful as compared to context free
00:10:28
language and final State
00:10:31
machines okay and in the next layer we
00:10:35
have this undecidable this is labeled as
00:10:37
undecidable and why is that it is
00:10:40
because the problems that cannot be
00:10:43
solved mechanically those kind of
00:10:46
problems it falls under this undecidable
00:10:48
layer like for example above uh some
00:10:51
time back we saw an example about a
00:10:53
problem that could not be solved
00:10:55
mechanically so those kind of problems
00:10:58
that fall they fall under this
00:11:00
undecidable layer okay so these are the
00:11:03
layers that we have to go through and we
00:11:05
will be starting with finite seit
00:11:06
machines FSM in the next uh following
00:11:10
lectures so we'll be start with the very
00:11:11
Basics so don't worry even if you don't
00:11:14
understand this terms that we used here
00:11:16
it will become very clear as we start
00:11:18
from the very Basics from the next
00:11:20
lecture onwards so thank you for
00:11:26
[Music]
00:11:28
watching
00:11:30
[Music]
