The school asks me to... all professors. The school asks all professors to, quote-unquote, do some attendance for the first few weeks. Now, officially, you do not have to... I know it sounds crazy. Officially, you do not have to attend, except you have to attend exams. And those will be stated in a syllabus forthcoming, which I'll talk about in a second. But the first few weeks, attendance has to be taken because the university gets reimbursed from the state based on how many people attend the class. So there we go. All right. Now, let's see here. How do I do this? Wait a second. Okay. I have to learn how to use this, what's it called? All right. So let me get the notes up and running here. There are some things we have to work out, just because this is not a... It's a new software. All right. In terms of syllabus and files that will be made available to you, that will be available on the Brightspace system under the content folder. Currently, currently, in order to get things started, I copied just temporarily files from a previous semester. So just... But I will today and tomorrow update them with current files, and I will email you to tell you as such. So you will get all the files that you need in order to do any assignments and to know what's going on. Since the first time. Since the first week, students tend to go in and out of class. The... What I... Instead of... Typically, in previous years, I used to spend the first day going over all the syllabus, et cetera, et cetera, talking a little bit about presentations and whatever. But I decided that I will delegate that to a media that I will post for you again sometime this week or... And we'll provide you notes for that media, the syllabus and presentation guidelines, which I'll talk about at a different time. So that you'll be able to, on your own, listen to, if you're interested, a discussion or hands-on discussion of the different aspects of the syllabus. But that is a... You know, whether you want to listen to that or not, that's up to you. If you feel that by just reading through the syllabus alone, the notes, which again, I will post for you. Currently, an older version is on the system. I will update it either this afternoon or tomorrow. Anyway, so I'm going to delegate that to a asynchronous lecture, which I'll post and you could listen to it or not. That's up to you. But that will technically be a lecture. I'm rambling through some things just to get us up and running. Okay, let's see here. Okay, let me share screen. Just saw it a second ago. Let me share screen. Where's share screen? Share screen? No. Doing meditations, no. There was a button here for share screen. Pump, pump, pump, pump. Pump, pump, chat. Participants, one second. We're going to share screen. Now share your screen, here we go. Select window. Okay. Mute website notifications. Sharing. Okay, why not? All right, let's see here. Now, ooh, that doesn't look too good. Well, let me ask you, are you able to see the Excel file that's currently posted? Is it a decent size? I guess you could. Yeah. Okay, good. I made it a little bigger. Is that better now? Can people see it? Yeah. Okay, good. Now... Okay, I'm gonna... I need to do a test with you, okay? I just typed something on the screen. Could you tell me what you... what it was... let me make it a little bigger. Could you tell me what I just typed on the screen? I'm doing a test here. Anybody? Testing one, two, three. Okay, very good. All right. So that's fine. So then that's good. And you're also able to hear me. I also do a sound check. You're able to hear me? Are people able to hear me? Yes, professor. Okay, good. Excellent. All right. All right. One more idiosyncrasy and then we'll get started in two seconds. And that is that the Brightspace system technically has meetings only for 60 minutes. Now, if I recall correctly, sadly having COVID a year and a half ago when I used. Brightspace, I think that if you're in before the 60 minutes, you could stay there. So I don't think we have to switch. But as a precaution, I posted... I emailed this to you last night. I posted... I created a second session, part one and part two. So there is a slight possibility around 60 minutes, meaning at 845, we will have to switch to... You would have to log in to a second part two virtual classroom session. Okay? But they're listed there. It'll be the dates and it'll say class one, part one, class one, part two. And that's only because our class is 75 minutes and the technical setting... The maximal setting for minutes on the virtual classroom on Brightspace is 60 minutes. But we're going to see if we're allowed to stay in the room. It could be that if you were not attending class and then you decided to attend, it could be that they won't let you in after 60 minutes. But by that time, class is almost over. So it's unlikely somebody will just show up. But anyway, so that we'll have to check. Okay? So we'll see if that's the case. All right. Let me get some other things here that I want to get for you. When I have it here. I see. So I don't have to do it that way. I can do it a different way. Give me one second. Yeah, starting things up is sometimes a little in the semester, especially when it's online. There's extra details that have to be done. All right. All right. Okay. Another little aspect here. I'm going to be putting in a whole set of notes which we're going to use. I already wrote up the notes. I edit and email you... Great. I edited... I edited... I wrote up a set of notes which I will email you later this afternoon. So I alluded to that at the end of my email last night which is that the school. The first page of the syllabus points that out as well. Which is the following that the school does... The school... One second. The school has a default for both copyright reasons and technical legal reasons. No one's allowed to audio or video record a class unless the professor says so. And I do not allow that. So the... Instead... Now, there are some students who are eligible for sets of notes. I won't go into... That's called accommodation, but that's not... The details are not important. But I... I conferred with the director of services and... Special services and he's... The director said to me that in fact... If I write up a set of notes for the students who were eligible... Then... Who otherwise could have recorded... Then they are not allowed to. So... That was a technical statement I had to make. But the bottom line is... I do not allow recordings, audio or video. And I will send to you. So anything that's on the board... Anything that I share with you... Will be sent to you. So you don't have to take pictures of your screen anyway. It will be sent to you. So... In the afternoon... I have classes till noon. And then in the afternoon... I read it over... Just in case for... Grammatical... And other things. And then I will... Email you... The... The full set of notes. Okay? Now... So the first item is just... In terms of communication. So the... My official Q-mail... Is... rgolberg.qc.c.cuny.edu. But because I have... 160 students each semester... From many sections that I'm teaching... I have to have... That the students... That's... When they send from their Q-mail... Should not send to my Q-mail... But instead... Send to a... Email... Which I only monitor... But I call it the... Class designated email. For this semester... That will be... CS722 Projects QC... At gmail.com. Okay? Even if you're... Undergrad or grad... The... There is a... Cross-listing. So you're either... Registered through... 381. Or you're... Registered through... 722. A little bit more about that... A different time. But anyway... Please send... You must send from your Q-mail... Because that's the only way... And I will send from my Q... If I send to you... To the class... I send from my Q-mail. If you have a question... Send from your Q-mail... Because the school guarantees me... That I know who it is. If you have... If you send it from... You know... Bluecheese... At yahoo.com... I will have no clue... And I couldn't verify... Who it's from. So... If you... You must send it from your Q-mail... But please send it to the class designated email... Which is... This email... Now... Because it's a new email that you have not yet... Received... Please... In other words... If I tell you that I'm sending notes... For example... I will be sending you a set of notes... Later today... In the afternoon... Sometime today... Anyway... Whatever... There are four different... What would I call them? Four different folders... That you have... That you have to check first... So the spam... For example... The spam... And the... Clutter... And junk... And trash folders... Which... So in other words... What I'm saying is... That the email I send you... Could... In fact... Go to any of those... So please... Do me a favor... Before you send... I didn't... Send me an email... Saying I didn't receive your email... Meaning... Let's say... The class notes... From today... Please check your spam... Clutter... Junk... And trash... Folders... Okay... Also... Please... Whenever you have a subject line... And when... The subject line... Of each email... Please put the two-letter code TC... Which is for me... Theory of... Computers... A Theory of Computation... There are different names to this course... Well... Technically... Under special... The rubric of special topics... It's... It's... Computability... And complexity... Etc... A classic name... For this material... That we're doing... Is Theory of Computation... So I... Designated... In each of my classes... So I could know... In the email... Which class you're referring to... Because sometimes students... Take more than one class with me... In the subject line... The first two letters... Designate TC... So for example... TC... And then... Dot dot dot... Please tell me... You know... It's the subject line... Of any email... Please tell me... What the... What the email's about... So I have a quick... Understanding... And I will try to... Get back to you... As soon as I can... Fine... All right... And there's a lot more details... But... Let's not... Deal with that now... Let's get started... Again... I will be posting... For you... Sometime this week... A... Media... Which will... Go through... The... Syllabus... Which you can... Either listen to... Or not... That's up to you... It's a... Technically... An... Asynchronous lecture... It will cover a full... 75 minutes... Class period... But... The... Lecture... So... If you find... Reading through the syllabus... Is sufficient... Then... You could... Save yourself some time... If... In addition... It will also cover... Presentations... Which I'll talk about... A different time... But... That... I'll put a link... Into that media... So that way... You could listen to that media... Independently... Of the syllabus... Because you may want to listen to that part... Okay... Anyway... I just need to drink something... All right... So... The... Three very popular names... To... The material that we'll be covering... One is theory of computation... Computability theory... Which is basically the same word... It's the ability to compute... And computation... The... The action of computing... The third one's a little bit more interesting... And that's called recursion theory... And... A major theme throughout the semester... Is going to be... Different modalities of recursion... The word recursion... In this context... Is... Certainly... You could relate to... From your knowledge of programming... And recursion... But it... It actually has... Broader implications... And we'll talk about that... Well... Throughout the semester... Okay... So we'll spend a number of... Lectures discussing that... All right... Two of the... Main... Some of the main... Contributors... Is... One is... Alonzo Church... In... In... America... And the other person... Alan Turing... In... In... England... Alonzo Church... Alonzo Church... Was known for... What's called... The Lambda Calculus... Some of you may have studied that... In programming languages... The modern... Java... In other words... The latest iterations of Java... Has... A little bit... Incorporated... A Lambda... Expression... Uh... The Lambda... Based on the Lambda Calculus... Of Alonzo Church... Uh... But he also... Contributed a major... Aspect... To the theory of... Computability Theory... And the person who... The person who really founded... Who put it all together... That aspect... Is Alan Turing... Uh... But... So we have... What we're gonna call... The Church Turing Thesis... Uh... Something we will discuss... The Church Turing Thesis... And... So... What's interesting is... They did not collaborate... In fact... It's not so clear... How much they knew... Of each other's work... Uh... But... Uh... Alonzo Church... Set... Uh... The setting... Set... The stage... And Alan Turing... Just took that concept... Which... I guess... By that time... It was known... In general... In the... In the... Field... And... Sort of... Solidified it... Alright... And then... You have... More... Theory... Asked... Formal Language Theory... Which is... A continuation of... Theory of Computation... Uh... And the major player there... Is a fellow... Noam Chomsky... Uh... Which we'll talk about... Now... Some of the... Fundamental notions... Of theory... Were based on... The mathematical notion... Of set... Set theory... And the person... Who's mainly... Uh... The... Contributor to that... As a fellow... George Cantor... Um... Now... All this theory... Was developed... Well... Not... Noam Chomsky... But the... George Cantor... From the late 1800s... Alonzo Church... From the 1920s... Alan Turing... From the 1930s... Uh... So that... Um... Uh... Was developed... Was developed... Before the onset... Of an actual computer... Right... It wasn't until the early 1940s... That there was... A stable... Electronic... Digital... Computer... Uh... The reason I say... Worded that way... Is because... There were some... In Europe... There were some... Attempts... To make a computer... But it wasn't... In Germany... For example... Uh... But it... Apparently... Didn't... Do too well... Uh... So the... American... Computer turned out... To be a more... Stable... And... Pretty much... People... Say that the... Uh... The... Iliac... Uh... Was the first such computer... In 1941... Approximately... Um... Okay... So... But this is... This set theory... And this theory... Is... Important... Because it sets the tone... For the... For the entire semester... So what is this... Church... Turing thesis... That I was referring to... Oh yeah... One more thing... Uh... If at any point... The... Um... The... The... The... Technology... The... Virtual classroom... Technology of Brightspace... Uh... Somehow drops... Um... Email me... And that's an emergency email... Uh... Please email me... At the... Qmail... Uh... Saying... Well... I guess we're using the other email... Let me see... It'd be easier if I do that... Yeah... Okay... So email me... At... CS722... ProjectsQC... At gmail.com... So please write that down... Uh... And just say that something went wrong... And I'll reboot... Or whatever... Um... I... It'll be a little hard for me to... Know... If... Uh... If Brightspace is... Carrying my voice... Or... If the screen is still visible... Um... Not that I'm doing anything... But... It's technologies... And it's over the... Uh... You know... Over Wi-Fi... And whatnot... So... You never know... So... I hope it's continuous... And we shouldn't have any problems... But... Uh... Um... Please... If at any point... Uh... You're not able to... Uh... Anything... If something goes... If you think something's happening... Email me... And I'll hear a beep... And I'll know to read it... Uh... The... At... CS722projectsqc... At gmail.com... And I will... Um... And I will... Um... Uh... What's it called? And I will... Reboot... Or try to deal with it... Okay... So the church... Turing thesis... States... Um... Okay... One more thing... Some people... Walked into our virtual classroom... Only recently... Uh... In general... As... As soon as you enter... Uh... The classroom... Please... In the chat... Text... The word present... That you're here... Okay... So if you have... If you haven't done so... Please do so... And from... Every class... Up... Subsequently... Please do so... Um... Again... The official roster... I only have to... Take attendance... For the first few weeks... Um... Can someone tell me... Is the sound... And... Sound and screen... Okay... By you... If somebody could... Respond... I'd appreciate it... Is the... Yeah... We're good... Okay... So let's continue... Good... Thank you... Every so often... I'll do that... Just to... Make sure... That things are going... Okay... Alright... So the church... Turing thesis... Is a rather... Mathematical... Statement... Uh... And when you first hear it... You're going... Oh no... What's this... What's this theory about? And what's the course about? But... It... It... Actually comes out to be... Something very... Uh... Very... Down to earth... Despite the fact that it's... It's clothed... In a very... Extremely mathematical concept... High-level math... And high-level set theory concept... Um... The... Why did they do that? Well you have to understand... There were no computers... Right? They were doing this... They were mathematicians... So they weren't... Trying to... Say... Hey... Let's... Create a... Material... That... You know... Are... The future generations of programmers... Uh... Will have a hard time understanding... They weren't trying to do that... They were taught... Their audience understood... Everything they were saying... And... That's who they... That's the audience they had... There was no computers... In the 20s and 30s... Right? There were no programmers... Per se... Uh... In fact... Although I haven't really... Uh... Been able yet to... Uh... Uh... As far as I could tell... The word programming... It was actually introduced... By mathematicians... And it didn't mean... What we mean... As programs... Uh... A program... Is... In mathematics... Is a system of equations... That you need to solve... For example... You may have heard the term... Linear programming... Or nonlinear programming... Right? The word program... In that context... Means a system of equations... Possibly subject to constraints... But system of equations... That you have to solve... Um... The point again being... They were mathematicians... They weren't trying to do anything. They weren't saying, hey, you know, computer science is just a technology. Let's see how we can beef it up and make it more scientific. They weren't trying to do that. All right, so let me tell you in a nutshell what this thesis is and in another nutshell why it's practical and then we will discuss the details to go through it. So, computability means the ability to compute. The ability to have a machine that can follow your instructions to solve a problem. Now, an important... another theme that we're going to be discussing throughout the semester was that they were not concerned, per se, whether your code actually does what you say it does. So, and that's... that's actually has a very interesting repercussion. But the point is they were not concerned with that. Your code does what it does. And as far as they're concerned, if the computer does what your code says it should do, that was a success. The fact that it didn't solve the problem you were hoping it would solve, it's not their problem. They're just interested interested to know, can a computer follow the instructions. They were not interested to know what... what is going to be produced by this calculation. Okay? They were just only concerned by that. So they weren't concerned with solutions. They weren't concerned with values. They were concerned with... well, we'll talk about what in a second. But it's a different, you know, axis of perspective. So please keep that in mind. Anyway, here we go. So computability, the ability of any machine to compute is based on countability, the ability mathematically to count. Now, George Cantor, a little bit of a tragic figure in a way, but that tragedy was a tragic figure. That aspect was not himself as much as it was imposed on him by the powers that be at the time. And, you know, it's a very interesting. There was a professor in City College who did a whole expose on this. And he has a tape. I think it was sold by the American Mathematical Society. Hopefully it's still there as a distinguished lecturer. It was a professor at City College who shows based on memoirs and handwritten documents that he found from the 1800s from George Cantor and from his wife, who actually refers to some of the work that he and her husband was doing. So the ability to count. So what do we mean by the ability to count? So what we will call, if you're not familiar, the natural numbers. And we in computer science start with the number zero. Now, when you're a programmer, especially when you learn the C or C++ languages or Java, you'll be told that in computer science we start from zero. The arrays, the indices of arrays, for example, start with the number zero. And they will give you a very interesting, based on addressing, reason why the name of the array is a pointer to where the memory is stored. And you could add the index in to get the actual address of memory. And the first location is index zero, because you don't need to move anywhere, right? The actual address of the array is the first spot. You don't need to offset and move elsewhere. Anyway, so that's what you're going to learn, is the reason why computer science starts from zero. According to theory, there's a more deeper reason why we must start from zero. Anyway, be as it may, the natural numbers, it's not really that big of a deal. You want to start from one, we throw in the number zero. But the count, you know, we actually count when you have items, you count from one. But the counting numbers got to start from zero. Anyway, those are called the natural numbers. The natural numbers is your ability to count. Okay? So, uh, you have, uh, if you count your key, the, the keys, the letters of the alphabet, A is, you know, the first letter, B is the second letter, C, D, E, 1, 2, 3, 4, 5, 6, right? And there are, what, 22 letters in the alphabet? Am I right? I think. Okay. Yeah, wrong. Uh, 26 letters in the alphabet? 26. Okay, 26 letters in the alphabet. Fine. Whatever there is. Um, so that's the ability to count. Now, what Cantor proved is that not every set of numbers are countable. Not, now, what, what does that even mean? So, the, the, let's, the, let's, uh, you know, take off the veil and say, who is that? Well, those are the real numbers. The real numbers are the numbers which we generally have a whole number, a decimal point, and then a bunch of numbers that represent the fraction, right? So, that, uh, our, uh, Cantor will, will prove are not countable. Okay. So, what, let's get an intuition why that's so. All right. So, I'm gonna ask a few simple questions, and I would like, in response, in the chat, give me what you, what, what is the obvious answer, okay? It's gonna, it's gonna sound trivial at first, purposely, but, um, here we go. So, if I say to you the number four, please tell me what, which number is the next number? So, please, in the chat, tell me what the next number is. Okay, good. Thank you. The number five. Excellent. Good. Wasn't that simple? Okay. We're just gonna do a few more. Okay. Uh, 4.1. Whoa. Anyway, five. Uh, five is the next number. Uh, in the natural numbers, five is the next number. Okay. Now, let's try nine. What's the next number? Ten. Beautiful. Okay. Good. Okay. Good. One more. Well, one more for the natural numbers, and then I have one more after that, which will bring the concept home, as they say. All right. And that is the number 15. Okay. What's the next number? 16. Beautiful. Are you ready? Okay. I've set you up. Uh, are you ready? Here we go. 1.5. One and a half. 1.5. What's the next number? 1.5. Okay. Ah, okay. So, so look, if, if, if, if one peeks at the chat, you'll see how many different responses you got, which is unbelievable. In other words, we're pretty advanced computer scientists. We've taken a number of math courses, and yet we don't have a consensus as to what the next number is. So, the real answer that, uh, Mauricio gave is there is no next number. Trick question. Wow. Such a simple question, and yet you can't actually answer it. When you deal with the natural numbers, the reason they're counting numbers is because you have a successor. You have a predecessor. You could say five. Four is the number beforehand. Six is the number after it. But if you say 1.5, so some of the students, uh, I see Ayub and, uh, and Rachel were, were trying to say, uh, correct that you, you could, there is no, you, you can't stop. It could be 1.5, zero, zero, zero, zero, zero, you know, and just keep adding more zeros and then, uh, another digit one. In other words, if you said 1.6, I could say 1.55, if you say, whatever you say. And in fact, in calculus, you learned this, or pre-calculus, um, and that was the definition of a continuous line, a continuous number, continuous curve. What's the definition? If you remember, they used to, I don't know, they used to use the Greek letters, lambda and epsilon. I don't know if they still do. But the point is that in any distance from where you are on the number line, so take the average, and there's always a point in between. So whatever number you would have said for the next real number after 1. 5, take that and average it with 1.5, and there's always another number in between. So it's impossible. There is no next number. There's no previous number. So how are you going to count? So this is not just a game. This is just an insight into some of the problems that real numbers have. Um, and Cantor showed based on this, well, playing this out, Cantor realized this, and creating through a technique, I don't think we'll have time to do, called diagonalization. Um, it was able to show that the set of real numbers, uh, is actually strictly larger than the set of natural numbers. And it's that size which caused, there are just too many to count. The counting, uh, algorithm breaks apart when you're dealing with the real numbers. It can't handle it. There are just too many, uh, you know, uh, what, what's that, uh, Jack Nicholson? Uh, was it, uh, Tom, was it Tom Cruise? Tom Cruise and Jack Nicholson? You are the truth. You can't handle the truth, right? And that's really what happened to George Cantor. He realized, uh, and not, and no one else in his, uh, uh, not many people in his, uh, in his, uh, time that he lived, his generation, were willing to handle the truth. But he realized that not, you can't count certain sets of numbers. Certain sets of numbers are larger than other sets of numbers. The real numbers are strictly larger in size than the natural numbers. Now, what, why was that so controversial in the late 1800s? Why, why it was so controversial is because, and this is a, uh, a very important lesson, I think, that you have to realize in anything you study, which is just because a discipline uses a word or a term, a key term, um, and you happen to relate to that term in a different context, does not mean that they're referring to the same thing. So the problem that arose, believe it or not, this has been documented by that professor in City College, I actually saw that video, uh, but again, you could buy it from the American Mathematical Society, uh, this, uh, expose on George Cantor's life and his work, um, is that the, the, the numbers of the natural numbers and the real numbers are both infinite. Infinite. Now, when, uh, uh, the, the, uh, um, the culture that was at the time that George, that George Cantor lived, uh, the mathematical journals were controlled, uh, mainly by the colleges in England, and the colleges in England were very religious. And they could not handle the fact that the, that the, the word infinite was used in, in a different meaning that they were mean, that they would relate to. Um, and believe it or not, and this is documented, uh, that they did not allow George Cantor to publish his work because they could, they didn't think that you can't handle the truth. The people at large would not be able to understand what's going on, how to differentiate what the mathematicians refer to infinite and what the religious circles referred to as infinite. In fact, I think the, uh, George Cantor actually, it's documented, I think he even petitioned, uh, the Vatican to, to get permission to publish it. Anyway, very interesting, uh, little story there, but the conclusion of the story is actually anecdotally very fascinating. What happened was, so for 10 years, he could not publish any work and his wife writes that that almost caused him to have a nervous breakdown because he knew that the mathematical world had no idea what the truth was. And he's the only human being who knew the truth about the mathematical sets. And, uh, so what happened was that, uh, 10 years later, a student of his finally grew up as it were. And his student became a, an editor of a, of a very low level journal. It wasn't a very good student. I mean, he was a good student, but he wasn't a top level student. So he became an editor of a, of a journal that no one, sadly, no one really cared about. Um, and, uh, he was visiting his mentor, uh, George Cantor. And, uh, and George Cantor shows him this proof because he knew his students would appreciate it. And, and, and then, uh, George said, but I'm not able to publish it anywhere because, uh, it would be, it would get too much, uh, it would be too controversial and the editors of the big journals won't allow it. So, so this, this actually happened. So, uh, the, the, the, the, the student humbly said, well, I'm the editor of a journal no one cares about. What you're gonna do is write a very trivial article that is totally meaningless and no one cares. You know, nobody doesn't say anything and I'm gonna publish it. And then I'm gonna give you a room in a footnote that you're gonna summarize your whole, the major point of your set theory. And the, whoever the powers that be, they're not gonna catch that. And they're gonna let the article be published and the word's gonna get out. And that's actually what happened. So he wrote an article, I don't remember what it was about, about nothingness. And, uh, in a footnote, you know, like Fermat's last theorem, right? The most important theorems are in footnotes and margins. Um, so he, he writes down a proof to show that the real numbers is greater in size than the natural numbers. Um, and, uh, that was it. It, it got published, uh, you know, and, and that was the end of it. So then the world finally figured, found out that it was true. But the, the, the assumption, which is to be more fascinating than the story, the assumption that just because some discipline uses a word or phrase that you happen to know about in a different context or use in a different context and then assume, well, they obviously mean the same thing. Uh, you know, that to me is wild. But anyway, so there are a number of words in math like that. Uh, but, uh, we're gonna bump into another one, uh, when we deal with non-determinism and, and, and, and philosophers are gonna somehow relate that to the concept of free will, which is an interesting, not very different story, but, uh, we won't spend too much time on that. But anyway, so that's what happened. So the natural numbers are, uh, counting numbers, but the real numbers don't have that ability, not because they're, uh, they are weaker, but because in some sense, they're stronger. They have more properties. They are, uh, too many of them and no, no, uh, counting algorithm has the ability to count them. Okay. Now, how does that relate to the church during thesis? So if I were to ask you, you know, let's take the number 100. Okay. The number 100. So very easily, uh, based using base 10 digits, right? Zero through nine. So number 100, please type in the chat. How many, what's the length of a hundred using based, uh, based 10 arithmetic? The number 100 has how many, how many digits? Three digits. Beautiful. Okay. Let's do one or two more. How about the number 1,000? How many digits does the number 1,000 have? Four. Okay, good. All right. One last one. How many digits does a number 20 have? Two. Okay. Now let's get conceptual. Let's get conceptual. And in the notes on the page, I discuss it and give you a little more, uh, more things that you know. But let's get a little more conceptual. Any natural number. Pick any natural number, right? That you have. The counting numbers. Give me a characteristic on the length of the number of digits you need to describe any specific, what, you know, it's a particular natural number. Whatever that natural number is. Ah, excellent. Thank you, Lauren, uh, and Rochelle, and Roshan, and all the, uh, everyone else as far, and all the others who responded. Correct. That's the key word. It's finite length. So as the notes point out, you can actually bound it. You, you, the fact is that, um, the, uh, any number, like, like I wrote, but you, and you could, in general, n will be less than or equal to 2 to the k. But the point is, there is some number k such that 2 to the power of k is the first power of k that's greater or equal to n. It's easier if you use n equal to 2 to the k, but you could do it less than or equal if you want as well. So there's an actual bound on the number, in the case of binary, because we're computer science, and, and generally our machines are binary. So there's an actual bound on how many digits you need. Namely log base 2 of n. Right? A very simple calculation. The problem is, take the number pi. Take a irrational, uh, a rational real number. Take an arbitrary real number. How many digits do you need to store an arbitrary random, uh, real number? For example, pi. And then the, uh, the answer is, as you're all saying right now, infinite. Okay. Now that is, that is key. That is key. Good. Excellent. Thank you all. So, why is that so important? And this is what Church and Turing realized. Church, Church really, well, Church realized this part. Turing also knew that, but he extended it in this very, very important way. Uh, but, um, Church knew that. Church was abstract. Church was just thinking in, in abstract concepts. Turing said, and I will provide you an architecture that will be able to, uh, adapt the concept. So that's why, which we call the Turing machine. But anyway, so that's why it's the Church Turing thesis. Okay. We'll talk about why it's a funny word, the word thesis. Why isn't it a theorem? Why is it only a thesis? We'll talk about that in a second. Anyway, now let's bring it home. So the, the Church Turing thesis says that computability is based on countability. The ability, the ability of a machine to compute is based on the ability of the machine to count. Okay. Only, you can only compute over countable sets. Why is that? So that's very highly mathematical. But we just gave the insight right now. What's that insight? The machine has, has to have memory. How much memory do you expect any actual real machine actual machine to have? Do you expect that machine to have a finite amount of memory? Or do you expect that machine to have an infinite amount of memory? Now, if you say, yeah, okay, please respond. Sure. Yeah. Okay. Some people are typing. Finite, right? That's, that's, that's pretty straightforward. Thank you all. Exactly correct. You expect the machine. You can't imagine a machine that has an infinite amount of memory. But you do understand that we have in fact, machines that have a finite amount of memory. Ah, but if you only have a finite amount of memory, then your machine can only store and generate numbers from countable sets. Because as we said, an arbitrary natural number needs a finite amount of digits and hence can be stored in your theoretical machine or even practical machine. But an arbitrary real number requires an infinite number of digits. Your machine can't actually store such a real number. So that's the church, that's the base, that's the true basis of the compute, of the church during thesis. The ability for any machine, any practical machine to compute is based on countability. The ability for the machine to count. Why? Because it only has, it's only as good as the amount of memory it has. And that memory is, which facilitates the computations, is only finite. It's based on the natural numbers and hence not based on the real numbers. So this highfalutin mathematics actually has a very practical down-to-earth statement. That's the church during thesis. It has a tremendous amount of repercussions, and we need to still ask about it, some aspects, and I'll mention it in a minute. Sorry, give me a second. Sorry, give me a second. Okay, now, so the, okay, good. So as we said, the natural numbers versus the real numbers. Now, the, the first question that pops up, perhaps, is, well, uh, but we know we have programming languages, and they provide us with real, uh, a data type called real. Right? So is that really real? Yes, I really like bad puns. I, you'll, if that, if it occurs through the semester, you'll hear me say them. I do not know why. I find them extremely funny. So you're gonna, you don't have to laugh. I'm not expecting you to laugh. Anyway, uh, I'll tell you one right now. At the end of the semester, I'm gonna say the final is finally here. Anyway, I'm just telling you ahead of time. Just to be aware of my, uh, silly humor. I have decent humor also, but I don't know why I find these puns funny. All right. So, uh, the, so the question is, what really is the real numbers that we get in a computer? So the fact is, and this is gonna dovetail a much broader discussion, is that the fact is they are in storage. They're actually only natural numbers. It's, we have a simulation. You treat them as real numbers, but they aren't actually real numbers. Okay. That, that's gonna be important. We'll discuss that, uh, probably won't have time today. We'll, we'll dovetail that discussion, uh, probably next class. Uh, another very, very important point is the following. We just said, because this is going to sound like a little bit of a paradox here, but, uh, but a very important point. Eventually, we said the church during, oh, oh, okay. Well, let, let me answer the point I said before. Why is it called a thesis? A thesis is shorthand for the word hypothesis, which means sort of suggesting that no one actually proved this statement. And yet, I'm telling you, this is the fundamental, uh, theorem, uh, involved in computer theory. The church during thesis is the fun, most fundamental statement or, or assumption in computer theory. But yet, it's only a thesis, hypothesis, conjecture almost, but not a theorem. So, oh, the, the, we, you know, the, the answer to this, and it's really wild, but the real answer, the correct answer is that just because you can't fathom a machine having infinite amount of memory, isn't a proof that there isn't an infinite amount of memory. The fact that, and this goes against all concepts of science, really, because science assumes, well, if you can't prove it, you have the right to assume it's not so. But computer theory is a little more humble than that and doesn't claim that. It's only a thesis, not a theorem. The fact that you can't imagine a computer with an infinite amount of memory doesn't actually mean it's not, um, it's not possible. So, it's only called a thesis, not a theorem. And I dare say, with the inroads that, uh, that, uh, scientists have been making in quantum computing, uh, while there aren't having, and haven't headed really in that direction, there are aspects of that which perhaps could suggest a models, uh, infinite memory models. But, uh, that's far from anything they have currently. But, uh, it'd be interesting to, to, to follow that, uh, that technology, to understand what, what comes out of it. But anyway, we currently believe and assume, and certainly the theory assumes, Church-Turing thesis, that you only have a finite memory model. Now, the irony, I don't know what to call it, what the word is, paradox, irony, oxymoron. If you're a literature major, uh, you'll know which one's best. But here we go. So, Turing suggests an abstract machine to implement Church's concept. Church said that all of computation occurs over machines that can count, that, uh, you could compute arithmetic over the natural numbers. And that is the fundamental machine that you, that does computability. Turing shows an abstract architecture, which we call the Turing machine, which will, will allow, uh, uh, any such, any such natural number of function, uh, to, uh, to run. Okay. Well, we will get into the details of that much later in the semester. But the, the one key point here, which I have to mention, is that if you, if you, I assume that some of you have already taken three 20 or you've learned it, but the, the, the interesting aspect is, and please text in the chat, if you know the answer, how conceptually, characteristically, you know, it's quality, how much memory did Turing provide in his Turing machine? How much memory? He used the device called a tape, right? A tape. And how long is that tape? So correct. So that, this is unbelievable. Turing is the, uh, Church and Turing are the, the, um, progenitors, uh, you know, the parents of, uh, grandparents of all computer theory. And the machine that Turing suggests has an infinite memory. We just said that Church, this, the fundamental assumption of Church, uh, is that all computation must occur over countable sets. We, we bolster that with the understanding that because we have a finite finite memory model and, and finite memories can only distinguish and count possibly natural numbers. Turing comes along and says, I have an actual architecture that could support these natural number computer machines, which we call the Turing machine. And the memory device that Turing provides is infinite. And, uh, that's unbelievable, right? I would think so. That's an unbelievable irony. Okay. So why did Turing do that? It goes against everything we just said. We just said that no, we're assuming that no machine can have an infinite amount of memory. So Turing had to do it for, uh, and we will repeat this point in different points, uh, because we'll, uh, because we'll pop up again and again. Turing provided an infinite amount of memory, not because the machine is going to use it, but he provided it so that Turing did never again has to think about space as a resource that he has to consider in his theory. He was bothered by the obvious problem, which is that if I give you a code, how do you know ahead of time how much memory you need in order to execute properly? What's the size of the resource of memory you need to execute properly, uh, your code? Well, so there are, you know, using different, uh, techniques of, uh, of, uh, complexity analysis, perhaps you could get decent estimates, but the fact is it's not a straightforward question. It's not a straightforward answer. It's not so simple to know exactly how much, um, uh, Ali asked a good question. So I'm not sure we're going to test this. Okay. So we're going to stay here. Uh, again, a year and a half ago, Ali Ahmed asked a very good question, which I mentioned earlier. Uh, technically Brightspace, the system we're on, the virtual classroom, only allows 60 minute, uh, 60 minute, uh, what you call it, uh, meetings. The 60 minutes will be up at 8 45 a.m. in approximately three minutes. I created a second part. In other words, for each date, uh, I, uh, automatically created part two of the class so we could be able to do the last 15 minutes. But I'm going to test it because I remember a year and a half ago that although the meeting can only be 60 minutes, um, that's only to start the meeting, in order to enter the meeting, at least a year and a half ago using the system, uh, it actually allowed us to stay in the room, uh, in the meeting, uh, for longer. So I'm going to test that out. Now, if, I'm going to continue imagining that we could stay. The problem is that, again, something may go wrong. So I'm going to ask you if at, uh, 8 45, 8 46, uh, something went wrong. Please email, meaning the virtual classroom just cut out, even though, even though the screen may be okay. But if you can't hear me beyond 8 45 approximately, um, or the screen for whatever reason shuts off, uh, at 8 45, um, the doomsday moment, uh, please email from your qmail to the class designated email, cs for computer science, 7 22 projects, plural qc at gmail .com. And just say, uh, it didn't work. And then we, I will immediately switch to the part two, but let's stay here and let's see what happens in, uh, two more minutes. Okay. Because it'd be great if we don't have to switch and save us time. So Turing included an infinite tape, not because he's going to allow any code to use the infinite tape. He just wanted to make sure that your code has enough memory, which is finite, to, uh, to, uh, run. And since he, he could not figure out, and it's not an easy problem till today, to actually figure out exactly how much memory you need to run your program. So he said, you know what, you have an infinite pool, use what you need. The fact is that the only way the infiniteness, infiniteness of the tape, his memory device, uh, could actually be used is if you have an infinite loop, the way he designed his machine, which I'll point out later in the semester. So the fact is that you're only going to actually bump into the infiniteness of his tape if something went wrong and you don't have a computation. Because Church's, Turing's definition of a computation is that it's a finite number of steps and the machine stops. Whereas the infiniteness will mean that the machine never stops, in which case you never get a solution and you never get a computation, as he will call it. Okay? Anyway, so that's the quick answer to his question. Um, so in the notes I mentioned the, this just here, uh, okay, and then there's another aspect, an interesting little twist here. Okay, we now have entered beyond the 45 mark. Um, uh, I only see part... that's fine. Don't worry about it, because you're here. Well, it, it disappears. That's I said, you can't enter the classroom after an hour. But are you able... could people text me if you're able to hear me, who are in the class now? Yes, good. Okay, so that's what I thought. So we could... I'm gonna continue. Don't go in... Perfect, perfect. Thank you, thank you. Uh, we're not gonna leave. So we're gonna try to do this straight. In which case, I believe, from now on, I'll have the part two as a backup. But we're hopefully never gonna need it. As far as I could tell, we could stay here. Um, and, uh, we could stay at... in this class till the end of the class. It's just as you pointed out earlier, who's, uh, whoever did it, thank you. Uh, Ali Ahmed pointed out that, uh, the... the the class meeting deletes itself in the listing. But we're still here, so we're good. All right, so let's continue. Again, if there's a problem, then... then email me at cs722projectsqc, and we'll have to move to... to part two. But let's assume everything's still okay. All right, Zeno's paradox. So let's... I throw this into our discussion of, uh, of finite versus infinite, continuous versus discrete. Um, those are other words that refer to the same concept. Because you're all familiar with it, it's a little bit anecdotal, but it's related to what we just said. So Zeno was an ancient, uh, mathematician. He actually existed. And, uh, it's a little anecdotal as to exactly the story, but apparently there was some, uh, question that a king, uh, asked Zeno. Uh, and they're different versions of the story, but they all boil down to the same mathematical or, at that time, philosophical question. So the, the, the, imagine you're in a, uh, uh, uh, you're at the door of about to enter into a classroom. And you want to walk to the, uh, to the other side. Okay? So if you, so the king asks, I walk halfway. Right? I walk halfway. Good. So you will enter and walk halfway. Of the remaining portion, you walk half of that. Right? And the issue is that if you keep doing this, you will never reach the other side. Right? Because as we said earlier, between any two points, between any two numbers, the, the average half between them is, is yet another point. So you'll never reach the second point if you always walk a half of the remaining distance. Right? The, philosophically, the king said, that's a problem because I know I could walk to the other side. So what am I, what am I doing wrong? The king asked. Why, why can't my algorithm of walking a half a distance, I got half under the, half out of the way, half out of the way. Why can't I do it? Why can't I reach to the other side? Okay. So, sorry. So the issue here, and I mentioned this above, well, again, discrete versus continuous, discrete versus continuous, et cetera. Continuous has numbers everywhere between all, you know, all, all dots, all points between any two points is represented by a number. Discrete, there are no, when you're one number and you have the next number, the successor number, there is no numbers in between, and we mentioned that before. When you're dealing with a computing device, right? Euclid said that you could measure the distance between any two points. In essence, Zeno's paradox was really a question on Euclid. Euclid studied geometry. Euclid said, you have two points, right? And there's a line segment between those points. But yet you could take a ruler and measure that segment, right? You could take a ruler, point one, point two, and measure it. So, Zeno's paradox applies. What's the paradox? How many points are there between point A and point B? You say the distance is five inches. Okay. So you have a point here, a point there, you take your ruler out, and the measure is five. That's a finite number. But please text, how many points are there between point A and point B? So in the chat, please text, how many, how many points do you have between point A and point B? Okay. Right. Thank you all. Infinite. Correct. That is, that was really Zeno's paradox. The story with the king, anecdotal, I mean, you know, whether it's true or not, either way. But that's the way, the popular way it was told. But what I believe is he was asking a question on Euclid. Euclid's geometry said, yeah, you can measure, with a finite measure, the distance from one point to the other. Presumably, that is comprised of points. So how could you have a finite measure of five summarizing the sum of an infinite amount of points? Right? How does that, how does that, how do you count up all those points? You know, they're an infinite amount of points, and yet the number is finite. Right? So what's, what's happening here? So this is based on the church theory thesis. When you're dealing with ages, measure is a machine. When you're dealing with a machine, you're dealing not with an analogue or continuous measure. You're dealing with a discreet or digital measure. Discrete and digital can't count, can't compute, the arbitrary infinite. There is an infinite amount of continuous points between the two points. You are using two different realms of calculations and you are overlapping them and then think you have a contradiction. There are an infinite amount of geometric points between A and B. But the machine only knows about a finite amount of them. Because a machine, the Church-Turing thesis, cannot compute over the infinite real number set. It cannot actually measure and count up all those points. So the measure is a digital approximation of sorts, but we treat it as if it's an accurate measure. We assume five, so that's it. The fact is that in the geometric sense, it actually is an infinite number of points. But the ability to measure it doesn't exist, according to the Church-Turing thesis, except in the digital discrete realm. And in that realm, it's a finite memory. It's a finite measure. So that's the issue that Zeno was dealing with, and that's related to our discussion. That we, again, we can have a data type called real number, but in fact, that's an approximation. We don't like to think of it in those terms, but in essence, that's what's happening. The machine can only handle a finite approximation. It cannot... it only has a finite memory, and it cannot compute that, or deal with all those infinite amount of points. Okay? Zeno's paradox, I mentioned here, this is a little bit of a... I call it a thought question, but it's a little bit of a homework question. You would have to dig up your 320 books to figure out the answer. Well, I'll talk a little bit about it now. I don't want to talk about too much about it because we don't deal too much with finite state machines. You deal with that in 320. A little bit I'll mention later when we talk about Turing machines to understand. Because the Turing machine does have embedded in it a finite state machine. But don't worry about that now. So, this issue of Zeno's paradox manifests itself in the computation of a finite state machine. I left it as a thought question only because potentially one of the hardest... as a teacher, one of the hardest tasks I have is trying to figure out how long... how much material can you cover in a given session. And sometimes you write down in your notes more than the session, and sometimes you write down in your notes less than the session. So, I thought at that time... The Imitation Game, was that the Turing machine was that the movie about Turing, Andrew? So, I didn't actually... Yes, okay. I didn't see that movie. It is a sad ending, I imagine, because... Well, there is a conspiracy theory about how Turing passed away. Some people think that they... that he was... well, whatever. The same... in America, the conspiracy theory is that... Marilyn Monroe was sort of dealt with by the government. And there was a conspiracy theory that Alan Turing was dealt with by his government. For different reasons. Very... if it's even any partially true, it's a very sad situation. And Alan Turing contributed from... as a scientist, Alan Turing contributed so much. He also... you know, the Enigma machine he solved the cryptography of the Luftwaffe. He broke their code. Anyway, but he... that's the same Alan Turing. Alright, anyway, so... But I'm pretty familiar with his life and his work. Even without the movie. So, Zeno's paradox with finite state machines. Yeah. So, if you recall from 320... Finite state machines deal with... Okay, you know what? Let me write in the notes since we're talking about it. So, finite state machines are provided... to process strings... strings over an alphabet. Right? And the idea is... to... the machine... should differentiate should be able to differentiate those strings... that are... members of a given language which we... the machine will be called acceptance, and the... those strings... over the... over the same alphabet that are not members... of a given language, and that... I would have liked a better name... but... the official name is called rejection. Those are rejected. Acceptance and rejection. So, that's what the... the finite state machine is supposed to do... in a nutshell. Okay? Uh... the finite state machine... in terms of a... structure... uh... in essence in essence... is a... uh... I just removed it... is a... weighted... uh can you shut off the sound, please? Don't... don't talk... while we're doing class. We still have three more minutes. It is a weighted graph. Okay? A graph a... weighted graph if I know how to shut your sounds... I would do so. I still have to figure this out. Uh... No mute. The mute I have here... There's still... Oh, settings. Hold on. Let me see. Audio. Mine. I don't know. All right. I don't want to deal with it. How do I exit this? I'll cancel. Here we go. Okay. Yeah, we're good. Yeah, we're fine. Good. Thank you. All right. So GW... graph W... will be equal to... whoever has their sound on... I hear your music. Please mute yourselves... so that it doesn't interrupt class. G... G... I'm sorry. It has a set of vertices... or nodes... has a set of edges lines connecting them... and then a weight function. And W will... will map... basically the edges to... usually to some real number some positive real number. Okay. In the case of finite state machines the weight the weight function is actually... instead of a number... is a letter. So it'll be a... a number... it'll be a... it'll be an alphabet letter. It'll be mapped to an alphabet. So the... each edge will be... will have a weight of a... of a letter, and you follow the edges along... some pathway... and you follow those letters, and that path... represents... so each path represents a given string. Okay. Now the assumption of... finite state machines is that... is that... that the... the machine only needs, and this is very important... that the machine only needs... It needs a finite amount of vertices to process an infinite number of strings that can be generated over an alphabet. So you have here the Zeno's paradox. How can a machine with only a finite number of vertices, a finite number of states, be able to process and distinguish amongst an infinite number of strings? So the Myhill, and this is the part you'll look up, it's the end of class, the Myhill-Nirod theorem answers this question, if you want to look it up. All right, it is the end of class. I will send you the notes later today, okay? Again, if you didn't have a chance, please text. It's one hour, 75 minutes. Our class ends now. It goes from 7.45 to 9 o'clock. No, no, it's not a paper. You're going to choose a paper. I'm going to ignore that for now. When I post for you the guidelines and I post for you the asynchronous lecture, they'll explain all this. But don't worry about it, Ayoub. We have time, okay? If you didn't have a chance, please text that you were present. Thank you all for attending. I hope it went well. And we will continue on Wednesday. Okay? Good. Thank you. Bye, all. I do realize there are kinks here that I have to work out, and hopefully I will. But we tried, anyway. So not bad for a first try. Okay. Thank you all. Bye, all.