The #1 Most Important idea in Computer Science
►► Audio, Video, and Transcript available: https://lispcast.com/the-1-most-impor...
►► Subscribe on iTunes: https://itunes.apple.com/us/podcast/t...
The idea of the Universal Turing Machine is incredibly important. But does your language support both properties?
Transcript
What is the number one most important idea in #computerscience? Hello, my name is Eric Normand. These are my thoughts on #functionalprogramming. This isn't exactly a functional programming idea, but I'm a #functionalprogrammer and this is the thing I think about.
Somehow, I guess that makes sense. This is my opinion on the most important ideas in computer science. This is the number one important idea which is the idea of the universal Turing machine.
I'm actually reading a book. It's an annotated version of Turing's paper that introduced the Turing machine. It's quite a good book. I recommend it to everyone. I'll have a link. I can't even remember the name. It's like -- that's it -- "The Annotated Turing."
The Annotated Turing. I've just been reading it. I don't look at the cover. It was recommended to me by Shmuda. You should check him out. He's an artist doing some cool work with the history of computing. It's awesome stuff. Link to him, too.
The number one idea is the universal Turing machine. I don't think we appreciate nowadays how significant this idea is and what we do every day. I'm going to break up the universal Turing machine into two parts.
The first part is the idea that you can have a machine that can compute anything that is computable. It's actually the definition of computability in the paper, in Turing's paper. That's part one. Nothing can compute something.
Let me say if the program is computable, it can be computed by a Turing machine. Anything that can compute anything is equivalent to a Turing machine. The Lambda calculus is equivalent to a Turing machine. That's cool.
A lot of people will use this argument of Turing completeness to dismiss discussions about what language is better. Like, "Oh should I use C or Java? Well, it's all just Turing complete anyway. I can do anything in my language that you can do in your language."
It's used as this last resort just to shut down the conversation. There's a second part that's often overlooked, which is that the universal Turing machine is a Turing machine definition that can run other Turing machines. Not only is it complete, but it can actually run itself [laughs] which is mind-blowing.
This part of the universal Turing machine is amazing because what it means is, is that any language can be the implementation language of any other language. You can write a universal program to run, or you can write a program to run any other language. This also has implications like, we're writing software.
We buy one computer and we can run different software on it. In essence, our computers are universal Turing machines that run software just data on the disk that gets fed to the processor. It can do anything.
We're living in a world of software. Think of the implications. This means that if I buy a computer, I don't have to worry that it's not going to be able to run some piece of software. It can run anything.
It's a computer. It's a universal computer that is running as a universal Turing machine. It can do anything that can be done, obviously, if your machine can run it my machine can run it. That's pretty cool. We don't have to worry about that.
That's like saying, "If your pipe can transfer water, my pipe can transfer the same water." That's awesome. It makes the computer itself a commodity and what's important is the software we run on it.
In 1958, John McCarthy published a paper that introduced LISP. It was meant to just be a notation for talking about computer software. It wasn't ever meant to be a programming language, not at that time. In the paper, he defines the semantics of LISP in terms of LISP.
What he did was he basically invented the first LISP interpreter by writing it in LISP which didn't run by the way. He had to write it, pretend it hardly existed and then show how to make it work. It's screwy. It's screwing with my head that he could bootstrap it like that.
Of course, it didn't work. Someone had to actually write the interpreter and assembly so that he could run code in LISP. Notice at the start of LISP, it had a proof that it was universal because it could run itself just like a universal Turing machine can run a representation of other Turing machines.