Episode 9: Introduction to Computational Theory
47:50 Share

The Theory of Anything podcast could use your help. We have a small but loyal audience and we'd like to get the word out about the podcast to others so others can enjoy it as well. To the best of our knowledge, we're the only podcast that covers all four strands of David Deutsch's philosophy as well as other interesting subjects. If you're enjoying this podcast, please give us a five-star rating on Apple Podcasts. This can usually be done right inside your podcast player or you can google The Theory of Anything podcast Apple or something like that.

Some players have their own rating system and giving us a five-star rating on any rating system would be helpful. If you enjoy a particular episode, please consider tweeting about us or linking to us on Facebook or other social media to help get the word out.

If you are interested in financially supporting the podcast, we have two ways to do that. The first is via our podcast host site, Anchor. Just go to anchor.fm slash four dash strands, F-O-U-R dash S-T-R-A-N-D-S. There's a support button available that allows you to do reoccurring donations. If you want to make a one-time donation, go to our blog, which is fourstrands.org. There is a donation button there that uses PayPal.

Thank you. All right, welcome to the Theory of Anything podcast. How's it going, Cameo? It is going great. Bruce, how about you? Good. So we talked about doing computational theory. So I went ahead and I prepared something quickly on computational theory, which is actually one of my favorite subjects. It may sound boring. I'm going to try to make the case.

That it's not boring. Computational theory is that class in computer science. I had a computer science major when I was a young guy. And I'm working on a computer science master's now, but I had a bachelor's degree that I did many years ago. And computational theory is that class that they make you take

that you don't have a clue why you're taking it. What it's about, why are they making me take this? It's got nothing to do with programming. It's got nothing to do with, as far as you can tell, anything to do with software. And they make you take it and it's super boring. And it's like this math class and you have to do proofs, which is like, you know, the bane of every student's existence is having to do proofs. You come out of the class and you like survive it and you go, man, I'm glad I'm done with that class. That was the worst subject ever. And then you move on with your life and never think about it again.

Nor do you ever use it again. So I was the same way. I thought of the class in that way. And when I was reading David Deutsch's books, he has computational theory as one of his four strands, one of the four most important scientific theories. First of all, that surprised me because I had never thought of computational theory as being a scientific theory. I thought of it as being math. And that's how most people would think of it. And that's how it gets taught in schools.

And so that's the first thing. And I'm going to explain why he says it's actually a scientific theory. It's really in between a scientific theory and math. It's the scientific theory that connects math and science.

physics together is what it actually is. Okay. And, but most people who teach it don't know that. So they don't know how to explain that to students and how to show what an interesting subject it actually is. They make it very boring. This is a, probably a deeper problem with classes in school is,

Low-level classes that are taught by teachers who would rather be teaching something else, and so the class is just not that interesting. And there's too many students anyhow. It's some giant one because everybody has to have that class, and it's got way too many people in it. It's in some semi-auditorium or something. Deutsch explains what it's really about, and it's like a really interesting subject.

And it really started to pique my interest. And of the four strands, this is the one that piqued my interest the most. So the four strands are many worlds quantum physics, computational theory, theory of natural selection, actually the neo-Darwinian, kind of the Dawkins version of it.

Right. Which is the most matured version. And Popper's epistemology, critical rationalism. Most people who get into the four strands get into critical rationalism. And I like critical rationalism too. And that was what we did our first four podcasts on. Right.

And computational theory is the one that I like the most, though. This is the one that, and it's a hard area, though. So, you know, I'm kind of more of a dabbler, but it was my interest in computational theory that got me to go back to school and get a master's degree.

Oh, really? Yes. And one of my favorite classes I was looking forward to until they made it maybe a little too hard was graduate algorithms, which is part, you know, it's a study in computational theory, which was very interesting, algorithms, which is the study of computational theory. And artificial intelligence, as you know, I'm studying artificial intelligence and machine learning. They have a special relationship to computational theory. In fact, they're almost like

a branch of computational theory almost. I don't know if anyone would believe that except me, but in my opinion, they are like a branch of computational theory. They have a very deep relationship with computational theory. So it's not an accident that I'm studying artificial intelligence and machine learning. It's because of my interest in computational theory that I chose that as my specialization.

I'm going to give you like a whole semester's worth in under an hour and kind of explain to you everything that they teach you in class, but you won't have to do any proofs and you won't have to do and take any tests. And you're going to make it so it's not boring too. Okay. So this example here that I've got for, for those that, um, uh,

if you're watching this on YouTube, you can actually see what I'm showing cameo, but you don't need that. I'll explain it so that it's something you can listen to on a podcast. There's an example here though of something called a finite automata or automaton in this case, there's a single one. And it's just a, you know how you go up to those little styles and you put in the coin and it lets you through like, you know, at Disneyland, I don't think I have coins at Disneyland, but

Something along those lines. Right. Sure. Okay. That's what this is. Okay. This, this, you know, you've, it's, it's, it's locked. You push it. It just goes back to lock. Cause you can't get through. You put in a coin. It becomes unlocked.

You try to put another coin that doesn't do any more good. It's already unlocked. Then you push through and then it goes back to lock again. Okay. Right. All right. So, and I can't remember where I got this example. I thought it was from Sipser, which is like Michael Sipser is the guy who writes the most famous book in computational theory. I could not find it in his book though, to credit him. I may have just found it as a famous example out on the internet.

But so this is an example of a finite automaton. And you probably wouldn't think of a gate like this being a computer, right? It's a physical object, obviously. But computers are physical objects, right?

Okay. And you could make a general purpose finite automata computer that you could then insert into a gate like this and it would work. But in this case, the computer is the physical object itself. That's more common than you might think, right? Because one of the things I'm going to explain is this, is that everything's a computation. So everything's a computer. All right. But

But a finite automata, which works with states and transitions like this, it can only perform certain types of computations. There are many types of computations that it's incapable of performing.

obviously there's no memory here like a regular computer would have. It's missing things that would be required for it to perform a lot of different types of computations you might want to perform. So fight on automata is a computer, but it's limited in the types of computations that it can do. Okay. Does that make sense? Yeah. Yeah. It's, it's essentially got a, a single, single binary process that it does. Yeah. Yeah. Okay.

Okay, and so any program that you could write with states and transitions, that would be a finite automata. You could run that on a finite automata computer. And keep in mind that these are theoretical computers. I doubt this would be useful enough that someone would go build a finite automata computer in real life. In computational theory, we're not so worried about

is someone going to build this in real life? We're trying to study the theory of it, right? So this is a concept that's important. Okay. Now you're probably familiar with regular expressions, maybe from,

from your job. As it turns out, a regular expression is a finite automata. They are one and the same. Any computation that a regular expression can perform is the set of computations that a finite automata can perform and vice versa. Now, that may not be immediately obvious at all because if you're familiar with regular expressions, you know it can do certain types of computations that are very useful, but

They're limited. You're not going to go program, you know, your whole application inside of just regular expressions. That'd be impossible. Right. So,

Now, how is it that we know that a regular expression is equivalent to a finite automata? Well, that's kind of an interesting question. Before I get to that, though, let me just point out a few other things. There is a probabilistic version of a finite automata that would be called the Markov chain, where you say there's a certain chance, if you're in this state, there's a certain chance you're going to transition to this state or certain chance you'll try to transition to this state. There's a non-deterministic finite automata, which is

That name is misleading. It really just means you can be in many states in parallel, which makes it, you know, at least theoretically more efficient in how it works.

moves through the program. However, a non-deterministic finite automata runs exactly the same class of programs as a deterministic finite automata. So even though it might be in theory faster, it is not more powerful. It cannot express algorithms or programs that a finite automata can't. You would think it could because it can be in multiple states, but it can't. So now, how do we know that a regular expression is the same as a finite automata?

Well, here's how a proof would be done of it, okay? So imagine that we've got, so we've got this class here, the deterministic finite automata. We're going to do deterministic because it's easier to do the proof. But in reality, since an NFA and a DFA are equivalent, this proof is just as good for the NFA, okay? And then we've got this class here called the regular expression. So what we'd want to do

is, and they, like, if you're taking the class, they would actually take you through the actual proof, which I'm not going to do. But they would show you that it's possible to take any finite automaton and it is possible to create a program, an algorithm that makes it into a regular expression. So there are no finite automata that you can't just transform into a regular expression.

Okay, does that make sense. So they would first create that proof. Yeah, yeah, absolutely. Okay, then they would do the opposite proof, they would say, now we're going to show that every regular expression can be turned into a finite automaton. So they would go through that proof. When you have both those sides of the proof, you've proven that the two are equivalent. Can you see that that's the case.

Yeah, absolutely. Yeah. Yeah. Okay. So this is, this is a big part of computational theory is the proofs where they're trying to like show this is equivalent to that, or this isn't equivalent to that. Things like that. Okay. Now there's another type of computer called a pushdown automata PDA. Okay. Not to be confused with public display of affection. No, no. You wouldn't want to confuse this, those two things. Yes.

So the only real difference is that it is, it's the same as a finite automata, but with memory, it's got a stack attached to it. You can push and pop from the stack. Okay. And then you can use that as part of the transitions. So this addition of the memory does in fact make it a more powerful type of computer. Now keep in mind that by powerful, what I mean is it can express more types of programs, types of algorithms. Okay.

we're so used to thinking of more powerful on a computer to mean faster. And that's a legitimate way of thinking of power, but that's not what we're talking about here. This is a much more fundamental concept of power. Okay. It's actually whether you can or can't express the program on the computer. Sure. So, um,

Now, a push-down automata, they're equivalent to something called context-free grammars. So I'm not going to get into that, but it's the exact same concept. You can show that you can compute one into the other and back, and then back again. Okay. So can you run programs on a PDA that you can't on a FA? Well, I already told you the answer is yes, but how would you prove that? Well,

Well, this is actually a little more complicated. So first we would want to prove that all programs on a DFA can be run on a PDA. Okay. So that's not too hard to prove. Basically the proof consists of this, this first transition DFA to PDA, the way you would prove it is you would say, well, if you don't use the stack on a PDA, it's exactly the same as a DFA because that's the way it's designed. Okay.

Okay. Therefore, I know that every DFA is also a PDA, that a PDA must be, has to be, can't be a subset of a DFA. Does that make sense? Yeah. Now,

Now, the second way, though, we're trying to not prove that they're equivalent, but that they're not equivalent. So we're trying to show that you cannot convert every PDA into a DFA. Well, that's a harder thing to show, okay, because you're trying to prove a negative now, okay? So they had to get clever about this, about how they're going to do this proof. What they did is they found a program that was possible to prove a finite automaton,

automata can't run, but that they could prove a PDA would run a PDA. Proving it runs on a PDA is easy. You just show the algorithm. Proving that it won't run on an FA was a bit harder, and I'm not going to get into the proof of this, but they were able to show this program can't run on an FA, but here is the PDA version of it. And that therefore shows that

that a DFA is a subset of a PDA. So a PDA is more powerful than a DFA because...

Because it can run every program a DFA can or any program that any finite automata can, not just deterministic ones. But it can also run programs that the DFA can't. Okay, so it is a more powerful computer. All right, you're with me so far on this? I am totally with you, yes. All right. So we therefore know that the PDA is more powerful than the DFA. So now there's, this kind of brings up a question.

Is there a most powerful computing machine or are there like infinitely many increasingly powerful computing machines? And we'll just keep discovering new, more powerful computing machines. Or is it max out? Is there like a certain type of machine that's the most powerful?

Okay. So keep in mind, we're not talking about running faster, having more memory. That's a different concept of power. We're talking about the ability to express algorithms or programs. Okay. So take a wild guess on this. What do you think is the correct answer between these two? Is there a more most powerful one or is there increasing infinitely many increasingly powerful computing machines? Well,

I think that there probably are, but I also have knowledge of a lot of theories that say there are not. So that wasn't an answer, but... Fine with me.

So this is a really important scientific and philosophical question. All right. So we're going to go through and try to answer that question based on what we know as of today by coming up with our best theories on the subject. Right. Okay.

So there was a guy named Alan Turing. You're probably familiar with Alan Turing. You've seen the imitation game, I would assume. Sure, sure, sure. Yeah. So excellent movie. Anyone who hasn't seen it, go, go watch it. That movie made him famous to laymen. But we were being taught about Alan Turing before,

way back when I was in, you know, computer science and he's been famous in computer science circles for computational theory, you know, since he was alive. Sure. He's at least a little bit considered to be one of the godfathers of computing.

He is considered the creator of computational theory. Oh, okay. Yeah. And as we'll see, he kind of shares that with Alonzo Church, but Turing probably went a bit further than Church on this. So that's why he kind of gets credit as the father of computational theory. Okay.

So Church and Turing lived about the same. They were contemporaries. And they both came up with hypothetical computing machines at around the same time. Okay. So obviously the computing machine that Alan Turing came up with is called a Turing machine. And that's the more famous of the two. And it's basically, it's a machine that can read and write off of a tape.

so you read the instruction off the tape or you can write something to a tape. And so he would start to work out like what class of computations can you do on this machine? You know, is it more powerful than a push down automata? You know, things like that. He was starting to work out a lot of this and church came along and his quote machine was really more like a grammar. So it wasn't a true where Turing actually conceived his as a physical machine.

that never really got built. I mean, it's been built by today, but it's just more of a curiosity. It was never intended to be built, right? Trying to make a computer with a tape that reads and writes would be maybe not the most convenient way to make a computer, but it's really easy to conceptually understand. And that's what's important when you're trying to teach this to students, right? So church is a lot harder to understand. It's this grammar that you use, but it does computations using the grammar.

And therefore could be considered a machine also. So the Church machine and the Turing machine came out around the same time. And Turing proved the two machines were exactly equivalent.

Okay. He came up with the proof exactly the way I just showed you that you can transform one into the other. And then the other one into it showed these are equivalent machines. They are nothing alike. They're, they're so different from each other. So why is it that these two machines turned out to be exactly equivalent? That seems like a really big coincidence. Okay. It's like, wow, we have these, these two smart guys coming up with computing machines and they're,

they come up with totally drastically different machines, yet somehow they're exactly equivalent. They can run the exact same algorithms as each other, and that's it, right? So it's like, wow, that's a major coincidence. Or is it a coincidence? Okay, so let's talk about how...

how this might have happened. Okay, so can two independently created machines, how can two independently created machines be equivalent? So what if there was a maximum amount of computing power allowed by the laws of physics? Okay, then the Turing and Church machines being equivalent is no coincidence at all. They simply happen to bump into the maximum allowed limit. Okay, and thus the

If that's true, then every machine we create will be equivalent to a Turing machine. We'll be able to prove it's equivalent to a Turing machine. So they tried to come up with other more powerful computing machines and they're still working on this problem today, right?

And one of my favorites was a Turing machine with a two dimensional sheet. So instead of having a single tape, you can actually move in two dimensions and you can read and write any, you know, anywhere on the sheet. Okay. You know, you would really think that that would make it more powerful than a Turing machine, but it doesn't. Okay. You can, you can always come up with a proof that this is exactly equivalent to a Turing machine and a Turing machine is exactly equivalent to it. Okay. In fact, every computer ever invented sense with a,

asterisk on the quantum computer is a bit of a exception. We'll have to do quantum computing as a separate discussion, but every computer invented sense has been proven to be equivalent to a Turing machine. So, okay. So why is that right? So let's, let's talk about modern computers first, because that may even be a little surprising that the Turing machine, is it really equivalent to a modern computer or a modern computer is more powerful.

Well, modern computers are actually a lot like Turing machines. So you have memory and you can access anywhere in the memory instead of having to move back and forward on a tape. But a memory is a series of cells you put values into that starts at zero and goes up to whatever the maximum number is. It's exactly the same thing as a tape, right? Right. So a modern computer is faster than a Turing machine, you know,

Obviously, a Turing machine would be incredibly slow by today's standards because it can access anywhere. And we've gotten this put into silicon and it's super fast because it's really small and things like that. But in terms of what algorithms can you express with a modern computer versus a Turing machine, actually, a Turing machine is more powerful than a modern computer, which is

which might surprise you. Oh yeah. Interesting. No, it's they're, they're cheating when they say that the Turing machine technically, since it's just, it's not a real computer, it's not, not a physical computer. It has a physical, it has an infinite memory. No modern computer can ever have an infinite memory. Right. So that's the actual difference between the two. Other than that, they're the same thing. Right. So, um,

And there's reasons why we hypothesize a machine with an infinite memory. And the truth is, is that there's not that much difference because you can always say, well, if I need more memory for this program, I'm going to go keep buying more physical memory and Veticomtube that can handle more physical memory.

And so based on that, we usually treat modern computers and Turing machines as basically equivalent. Even though in theory, a Turing machine with its infinite memory will always be able to do something that the modern computer can't until they're able to get more memory for it. Right, right. Okay.

So can we prove that a Turing machine is a most powerful computer? All right. Well, up to this point, we've done everything through proofs. We proved that a finite automata is equivalent to a pushdown automata, things like that. And this is really perceived as a branch of math where everything is done through proofs.

So they weren't quite ready for the fact that there doesn't seem to be a proof that the Turing machine is the most powerful computer. Oh.

And no one's ever been able to come up with such a proof. And in fact, I'm pretty skeptical that you could come up with such a proof and I'll try to explain why. So how would you go about proving that there could never be a more powerful computer? I don't think you can, right? There's always the possibility, I guess, that there would be some computer we just haven't thought up yet that could

can do things that the current computer can't do. And like I said, the quantum computer actually qualifies slightly as that type of computer. It can do some things that a Turing machine can't. The difference seems to be between, it can do some things faster, but remember we don't count faster. So it can express analog instead of digital, which makes it slightly different, but not in a way that, I mean, like, I don't know if we know of specific,

algorithms that you couldn't just approximate to any level that you would desire on a regular Turing machine. So it's not as much of an exception as you might think, right? It's still processing pretty close to the same class of algorithms. Okay. So, um, and the excitement around quantum computers is more how it can do something so much faster and we'd have to get into why that is. Um,

and it's actually relevant, strongly relevant to computational theory. By the way, David Deutsch, who inspired this podcast and it's his four strands that we're talking about. What he's famous for is creating quantum computational theory. So he was the first one to come up with, he's the, he's the Alan Turing of quantum computation. He's the one who came up with quantum computational theory and proved that it could do some things that, um,

a regular term machine couldn't. And he's the one who kind of started the whole quantum computation revolution that we're still trying to engineer. We still can't really build them real useful ones yet. Right, right, right. We can see some promise, but we don't actually know how to use it. The thing that really got people excited about quantum computational computers was

was Shor's algorithm, which is an algorithm that can crack any encryption, any RSA type encryption. Actually, I should be careful there. There are types of encryption it can't crack, the regular pad encryption, things like that. But those are not as useful. And so the type of encryption that we use widely to protect your credit card or to protect, you know,

government secrets or something like that, it can crack that type of encryption. So Deutsch points out that because Shor's algorithm already exists, we just haven't instantiated a computer that can run it, that in a sense, all encryption is already cracked.

So like if you're the Russians, you are already storing every encrypted secret that you can from America. And then you're waiting for the quantum computer to be invented, to be engineered. I see. And then you're reading them all. Right. And so in a very real sense, all encryption is already cracked. People don't realize that, but it's the truth. Okay. Because it's just a matter of time before we actually engineer a quantum computational computer. And it's in a separate context.

Podcast I'll talk about like how it works, but it's really freaky what a quantum computer can do because it uses, you know, quantum mechanics. And since quantum mechanics is based on superpositions and entanglement and things like that. It can do computations that are larger than the number of the atoms in the universe.

Oh, okay. And the reason why is because it's using the multiverse. So it's doing the computation across the multiverse instead of inside of a single universe. Sure. And so that's why it's able to work faster than any other, you know, regular Turing machine. Okay. So now we have already proven the theoretical existence of machines more powerful than Turing machines. So it's not like we can't conceive a,

a computer that's more powerful than a Turing machine. There are such things as super Turing machines, but they violate the laws of physics. They can't be built in real life. Right. Okay. And so this, and this is one of the reasons why I have my doubts that you're going to see some more powerful type of computer someday, even though we won't be able to prove it.

is because we are really talking about the laws of physics at this point. We're talking about what do the laws of physics allow? Okay. So, you know, maybe some future theory of physics might allow for a super Turing machine, but I don't think it's happening under any current theory of physics, right? So it's,

Who knows? I mean, as we study quantum mechanics, I'll have to find the quote, but Roger Penrose quotes David Deutsch as claiming that there's certain types of Oracle machines they might be able to build, which would therefore be a super Turing machine computer. But we don't currently know of any way to do that. So they finally gave up on a proof and they called this, they made up something called the Church-Turing thesis because it's not a proof.

All right. The Church-Turing thesis that later got modified to be the Church-Turing-Deutsch thesis to take quantum computation into consideration. But I'm generally going to drop the Deutsch side of this because it's too hard to explain quantum computers quickly anyhow. So we're just going to refer to this as the Church-Turing thesis. Okay. And Deutsch points out that this thesis is...

is really a full-on scientific theory. Okay, now people don't think of it that way. You can almost see it as like a scandal that we've got this really important principle in computation called the Church-Turing thesis. It's the basis for all of computational theory, and yet we have no proof for it. Well, Deutsch points out, well, actually, it's a scientific theory. There are no proofs for any scientific theories because of the reasons we talked about in our previous podcasts.

And in fact, this is really a branch of physics. So of course there's no proof of it, right? Okay, so this isn't necessarily a big deal that we have no proof of the Church-Turing thesis. Once you start thinking of it as a best theory, you know, it's our best theory,

theory of computation, it's our best scientific theory, and start thinking of it as a scientific theory, then it's unexceptional, right? It's just the same as any other scientific theory. It's the best we could conjecture and come up with, and we know of no counterexamples. And there's no competing theories. There's not some alternative theory of computation out there that we're still looking at, and it's a strong competitor. It's got no competitors. It is the sole theory of computation that exists, right? Right.

Right. So because of that, that makes it special. And this is what we talked about in our first four podcasts.

When you've got no competing theories, that's your best theory. You should accept it as the truth. Tentatively, yes, but you should accept it as the truth and you should think through what are the ramifications of it. Okay. So now I claim here that it's the church Turing thesis. When you think of it as a scientific theory is the single best tested theory ever created. Now there are people who would definitely argue with me over this and I

In fact, usually what you'll hear is that quantum theory is the single best tested theory of all times and that we don't have a single counterexample to it. Okay. Like even Einstein's general relativity, we know situations where it breaks down like in black holes. Right. Where it doesn't work. Quantum theory, we don't know of any exceptions right now. And,

It can be tested to, you know, even though it's a probabilistic theory, you can test it to like, you know, the 10th decimal place or something like that, right? I mean, it is a super accurate theory, you know, way more accurate than any other theory we've got, right? So a lot of people would say quantum theory is the single best tested theory. Well, I'm going to point out that every test of quantum physics is also a test of the Church-Turing-Deutsch thesis. Therefore...

Therefore, by definition, the church Turing thesis is the single best tested theory we've ever had. And in fact, I'm going to go a step further than that. And I won't get into it in this podcast, but the, all of science is actually based on the church Turing thesis, in my opinion. Okay. Which means every theory of science is also a test of the church Turing thesis. Therefore it would be impossible for it to not be the single best tested theory in

in science. These are bold words you're saying though. Yeah, they are bold words. I'll have to justify them in future podcasts. Okay. And you know what, just as a, just as an overview for that though, consider the fact that math and science are so deeply tied. Right. I mean, it would be hard to imagine physics without math.

You wouldn't take seriously a physics theory that wasn't mathematically based. No, absolutely not. But math is Turing compatible. So the very fact that it's a mathematical-based theory makes it a computational theory, therefore makes it relevant to the theory of computation. Whether you can compute it or not is still determined by the theory of computation. So every theory that's at least mathematically based

is also a test of the Church-Turing thesis. That part should be obvious. Right. A place where I might get some pushback is on theories that aren't mathematically based. I would argue that they're still algorithmically based, that you can't even explain something to a human being without putting it into something that's equivalent to an algorithm, where they understand this implies this. So I would argue that all scientific theories, in fact, all explanation, all rationality, is rooted in the Church-Turing thesis. Right.

Okay, so what is the church Turing thesis? You'll hear it stated in different ways. I'm going to state it in a way that is correct, but is maybe not the way most people would think of it. So what it means is it is not possible to come up with any sort of computational machine that could perform a logic program that a plain old Turing machine can't. Okay, so that would be one way of stating the church Turing thesis in layman's terms.

Okay. Which means that Turing machines and their equivalents are the most powerful possible type of computational machines. And there are no more powerful ones out there that we just don't know about yet. Okay. That is the church Turing thesis, which is scientific theory. It's not a mathematical proof, but that is our current best theory on computation. Does that make sense? Yeah, it does. Good. So what's the Turing principle now?

Roger Penrose is the one who created the term Turing principle. And it's actually the same as the Church-Turing thesis. However, Church and Turing had a difference of opinion on this. And so Church was a little more shy about it. So Church took the Church-Turing thesis to simply mean every algorithm that exists can be run on a Turing machine, which left open the possibility of something being non-algorithmic.

Okay. Turing couldn't, didn't, didn't think there was such a thing as non-algorithmic things, right? Which is what I just,

claimed a moment ago. Right. And certainly if I were to say, you know, give me an example of something that's non-algorithmic, you know, you might be able to come up with something that's really vague. We don't understand well, and then I can't give you an algorithm for it, but it doesn't mean an algorithm doesn't exist. Right. The truth is, is that it's not clear what we even would mean by non-algorithmic. So Turing took it to its, its logical conclusions. He points out, well, actually everything's algorithmic. Therefore,

the Turing principle is equivalent to the church Turing thesis. And the Turing principle is that there are that, sorry, the Turing principle then is the idea that everything in nature can be simulated on a Turing machine. Cause it's just the laws of physics, right? If there was some sort of thing that the laws of physics allowed,

us to physically do that you couldn't simulate on a Turing machine, then we would build a computer out of that physical process and we would then have a computer that was able to do it. Right. Okay. And this is the sense in which everything is a computation. Everything is equivalent to a computation. And so taking the position there are computers more powerful than Turing machines, we just haven't discovered them yet.

You could take that position. Nothing stops a person from taking that position. For all I know, it's a true position, right? But it would violate the Popper's epistemology of, the reason why is because we're now comparing an explanation, our best theory, Church-Turing thesis, to a non-explanation. That statement, there are computers more powerful than Turing machines, we've just not discovered them yet, is not an explanation. It simply spoils a good explanation. Right.

A good explanation version would be, here is this computer that is more powerful than a Turing machine, and here is how it operates. Right? That would be a competing explanation. We don't have one of those. Okay?

So that's actually it. This is my first part. I'll have to go in deeper in future podcasts as to like what you can do with computational theory. And then ultimately, what are the philosophical ramifications of computational theory? Just to maybe give one example of that, though, because I think that this is interesting. I was talking with a lady that is a neuroscientist. She's a PhD in neuroscience. And

I was explaining to her my interest in artificial general intelligence. And she was wondering out loud, is it actually possible to build an artificial general intelligence? And I said, yeah, it is. She goes, you can't know that. I said, you're right, I can't know that. But yeah, yeah, it can be done.

And she said, okay, well, how do you know that? I said, because the brain's a computer. And she goes, well, no, I don't know if I buy that analogy. I do know many neuroscientists who buy the brain is a computer analogy, but there's others that don't. I said, no, it's not an analogy. The brain is a computer. Okay. Did he get frustrated with you at that point? Yeah.

Okay, but what I'm really saying is, is I'm saying the brain follows physical processes. Physical processes can be described by the laws of physics. The laws of physics can be computed on a Turing machine. Right. All of those are non-contested theories, right? I mean, they're literally just, there are no known exceptions to that, right? So when people try to make the statement that you can't build AGI on a computer, right?

what they're imagining, whether they realize it or not, what they're imagining is that the brain has biological processes that violate our current understanding of the laws of physics. Interesting. Okay. And you know what? For all I know, that's true, right? We always hold our theories tentatively, our best theories tentatively, but I don't really take that point of view seriously yet because

Because there's no explanation for it. There's no competing theory I can point to. When somebody actually creates that competing theory, then I'll look at it. Then you'll consider it. Right. Right. But until then, there's an infinite number of such non-explanatory

explanatory theories. I don't really have the time to be looking at them. And I don't even know how I would go about looking at it seriously, right? So, and of course they don't realize they're saying that. There are people who do realize this. I think most people who say these things have no clue that they're claiming that the brain is doing something that violates our current understanding of the laws of physics. Roger Penrose is a really interesting exception to that

I just listened to an interview of his. In fact, I'll get you to listen to the same interview and then we'll do a podcast discussing his viewpoint. Okay. But, uh, right. And I mentioned him before. He's the guy who was the teacher for Stephen Hawkins. Right. And he's like super smart and one of my favorite authors, but I like disagree with all his conclusions. And, and,

And in the interview, he just says it outright. He says, no, I'm going a lot further than people think. I'm not claiming that the brain is a quantum computational process because a quantum computational process is still equivalent to a Turing machine. He understands that when most people don't. Right. He says, no, I'm claiming that quantum physics has a non-computable process in it that we just don't understand yet. Right.

Okay. And that we're going to eventually have a new theory of quantum physics. So he's throwing the current theory out altogether. That's something that people miss. There's going to eventually be a new theory of quantum physics that includes non-computational elements to which, and this is the thing I would, if I, if like I could have him on an interview, I would ask him this, how would we even understand what it is? You can't describe it with math.

I mean, it would forever be opaque to us as to what it's doing. We try and reject things that we can't describe with math. That's correct. And we're right to. And this is something that falls out of Popper's epistemology. We're right to reject things that...

that by definition we think are inexplicable, right? We always should be seeking an explanation. Well, and this is so, you know, we had talked briefly, I think it was on the last episode about the people who apply kind of a metaphysical, um,

almost religious element to quantum physics. And I think that it's that part of the whole theory of quantum physics that is appealing to them. They're sensing this, like, here's this answer for the things that we cannot describe.

That's interesting. And you know what? And this is, we need to do a podcast on, in fact, I'm working up towards eventually doing a podcast on many worlds quantum physics. But the reason why people hide mysticism inside of quantum physics is because once you claim there is no explanation, you can hide anything in it. Okay. That is a truism. Right. Okay.

From the moment that the Copenhagen interpretation of quantum physics became the most popular, it's probably not the most popular today, but it was the most popular for a very long time. It took the stance there was no explanation to certain aspects of quantum physics. The upshot of that, of assuming that there is no explanation and that there's no reason to even seek one, is that you can hide anything.

Anything in it. Oh, interesting. Okay. And that's why until many worlds takes over, which it's slowly doing, but until many worlds takes over, there will always be people who want to hide mysticism inside of quantum physics because it has no explanation. Right. And you can go to your physics teacher and they'll tell you there's no explanation. Right.

Right. And don't worry about it. Right. They're saying this is an invalid question. Don't even ask it. Okay. And that is what most physics teachers, professors around the world today will tell you. And that is the danger of them telling you that is that

They're opening that door up to anything. You know, there's a principle in mathematics too that's exactly like this, which often I show it to you sometime, but there's a proof that if you can show that a system of mathematics allows for any one contradiction, then it allows for every contradiction. Mm-hmm.

Okay. And so it basically undoes the whole system of mathematics. And so if you ever allow a single contradiction, then you can prove anything to be true. Everything is true at that period. Okay. Which is why allowing even one contradiction is just horrifying. It destroys the whole system of mathematics. Okay. Goldil's incompleteness theorem was based around

attention over the fact that either every mathematical system is either contradictory or it's not possible, it's not consistent, you can't prove every truth. Everybody immediately accepts it must mean you can't prove every truth because that one doesn't destroy the mathematical system. It's often viewed as unfortunate, which is actually unfortunate that it's viewed as unfortunate, but anyhow, it's often viewed as unfortunate.

But everybody gets it that the moment you say I'm allowing one contradiction, boom, the whole mathematical system is pointless, right? And unfortunately, quantum physics is the same way. If all of physics is built on quantum physics and it allows for non-explicit,

explanatory, it has no explanation for certain phenomena in it, then absolutely anything can be fit there because it's the same principle, right? It's the idea that now that I don't have an explanation, I can just insert whatever explanation I want, right? And they're all equally good at this point. Anyhow, that's maybe a preview for a future podcast when I talk about this.

Which is one of the reasons why many worlds is actually really important to understanding quantum physics. Right. So, because it actually explains all these things and it basically wipes away the mysticism, right? It says, no, here is the explanation. And it's completely, it's not that hard to understand. The idea that you can't understand quantum mechanics is not true. It's not that hard to understand. It's just...

it's there's multiple worlds and that's what's going on um so anyhow i think it's important always um to tie everything back to really good sci-fi um so um in uh verner vinge i think you know he's one of my favorite sci-fi authors and and very much um

the way he has handled these limitations is to create in his, in at least one of the universes that he's created, this concept of zones of thought is what he calls them, in which

different things are in which the laws of physics are different and the slow zone in which we live in it biological intelligence is possible but artificial intelligence faster than light travel are not possible faster than like communication is not possible and it's not until you get to the next

of actual physical space within the universe where things like artificial intelligence, true artificial intelligence is possible. And then as you continue to move into other zones of the universe, you get to higher areas that he calls the transcend where super intelligent beings live way beyond our concepts of even being able to understand. Yeah. Interesting.

It's how he's gotten around this limitation because he totally acknowledges it and says that this is the only way that he can figure out to get past the limitation of physics is just to create places where those laws are different.

Interesting. And you know what? That's not entirely off base. If the laws of physics were different, we could build different types of computers that can compute different things. That's... I mentioned that in passing, that we can conceive of computers, but we just...

that are non-Turing machines, but that they violate the laws of physics. What that really means is if you had a different set of physics, you could build different computers that have different repertoire of algorithms. Right. So Fire Upon the Deep is the particular novel where he gets into it very, very deeply. Recommend it. Fire Upon the Deep. Okay. I'll have to add that to my listen list. Okay.

Okay, so let's wrap it up for today then. All right. Thank you, everybody, for listening to us.