Let me say a few words on the fourth chapter of Scott Aaronson's book, Minds and Machines.
It's about complexity of problems as well as the differences (or equivalence) between human brains and artificial thinking machines.
When one reads this fun stuff, he may see how these complexity folks are thinking and – even if he knows the principles – he realizes which of them are considered important (and, in many cases, more important than they deserve) by the complexity theorists.
I would say that not even Aaronson would claim that this chapter has anything to do with physics but I have been surprised many times in my life so I am not certain.
Mathematical problems may be easy-to-solve or harder. We may order their difficulty in a way. Two problems may be equally (qualitatively) difficult. If one is harder than another, it means that an algorithm to solve the former implies the existence of an algorithm solving the latter but not the other way around. And so on. Are there intermediate difficulty problems between two known classes? You can imagine what he writes about.
A central thesis worshiped by these complexity theorists is the Church-Turing thesis: algorithmically solvable/calculable problems are exactly those that may be solved/calculated by a Turing machine – a particular structurally simplified model of a universal enough computer.
The complexity theorists including Aaronson are clearly impressed by this thesis. Your humble correspondent – and, I believe, most theoretical physicists – would decide that the thesis is mostly ill-defined or a vacuous tautology or potentially wrong, depending on the definition of "algorithmically solvable problems". The complexity theorists' obsession with the thesis and similar theses may be a part of the reason why they haven't done too much genuine progress in artificial intelligence and other things, as discussed below.
Their excitement isn't too difficult to understand. The key insight is that all intelligent enough thinking is in principle the same activity. Even if you have a different architecture of a microprocessor (80386, 6510, ARM...), you may still employ the chip to interpret a programming language. An interpreter of another programming language may be written in your preferred programming language which runs on any computer deserving the name; the task to write these interpreters is more or less straightforward. So all computers and languages may simulate each other so they're equally potent. To some extent, this must hold about differently thinking human brains, too.
It's great to realize this fact about the universality of computation but once we realize it, we should also realize it's vacuous.
(The Church-Turing thesis may be more than a vacuous statement but one would first have to give an exact definition to the "algorithmically calculable functions/problems" that don't refer to a particular machine. Clearly, this required definition will refer to some particular machine or some particular machines, and for different choices, the Church-Turing thesis may be both right or wrong. If you build the definition on Turing-equivalent machines, it will be right and vacuous. If you insert some other hypothetical machines, probably physically impossible ones, it may be wrong. Garbage in, garbage out. You don't learn anything.)
Physicists are also enthusiastic about similar equivalences of something – namely theories – but they only become elevated in the case when the equivalence is more surprising and nontrivial than a straightforward translation of a program from one programming language to another. When the equivalence between these theories is surprising and hard to prove, physicists call it a "duality". Exactly because it's not trivial, a duality is very potent. It seems to me that the complexity theorists never switch to the mode of thinking in which they call a spade a spade – in which they decide that a trivial insight is trivial – and that's why they sometimes remain stuck in the quagmire of trivial and vacuous insights.
After all, the chapter also mentions that Turing correctly predicted that the capacity and performance of the computers would grow by a huge (nearly realistic, it turned out) factor within 50 years. But he incorrectly predicted the rise of artificially intelligent machines that would become indistinguishable from humans.
Another idea that Aaronson's criticizes is "meat chauvinism", namely the assumption that thinking machines composed of proteins (a set that includes a majority of commenters on this blog) are more conscious or intelligent etc. than artificial machines etc. If a computer program simulates a human, it or he or she must be given the same status and "approved consciousness" and human rights, Aaronson thinks.
Well, I have mixed feelings about that. More precisely, I agree that 1) the inner functioning is a more essential part of an intelligent device and its "identity" than the precise nature of the transistors or cells or technical architecture, but 2) the clever computers clearly don't have to be given human rights. It's up to people or a society – at least as long as the people are in charge – whether they respect the human rights of such computers. As I have argued many times, science cannot answer moral questions.
The very usage of the word "chauvinism" shows that Aaronson is prejudiced in these matters – and his opinion differs from mine. This word "chauvinism" is arguably meant to sound negative – at least that's my conclusion after years in which extreme leftists were surprised when I felt proud after they identified me as a chauvinist of any sort. But let me tell you something: chauvinism is often a great and essential policy. For example, computers may be equivalent to humans in many respects but they're not equivalent in others and it's legitimate for me and every other voter or politician to consider the replacement of humans by computers undesirable. So from my viewpoint, it's right to "discriminate" against computers.
But I don't want to talk about these "political questions" only – even though the number of essays criticizing PC, egalitarianism, and similar junk ideologies is never high enough. The very idea that a smart enough computer could be "really equivalent to a human mind with all of its consciousness etc." could be wrong. In particular, if you create a classical simulation with a random generator that "behaves" indistinguishably from a quantum system, it could be fundamentally a different thing when it comes to its consciousness etc.
I am referring to the Conway-Kochen free will theorem. The randomness implied by quantum mechanics may be shown to arise locally in the very region where the value of an observable is decided for the first time – that's what is meant by the "free will" here. However, this property is violated if you supplement an artificial engine with an external random generator. In that case, the decisions are really made by this generator where a big part of the "identity" lies. And you don't want to give human rights to a random generator because it's just too dull. Again, science doesn't imply what the right policies are but because there is a fundamental feature in which the actual quantum object and its classical simulations are inequivalent, it's surely legitimate to treat them differently. (Every ideology claiming that A and B should be treated equally in situations C and D is based on the fact/claim that A and B are equivalent in some respects E, F while totally overlooking the fact that they're inequivalent in other respects G, H: it is always an example of an ideological cherry-picking.) I don't say it's desirable or necessary. It's just a sensible possibility that some people may prefer.
At the end of the chapter, the author solves a problem from the previous chapter. Spoilers follow. The \(n\)-th Busy Beaver number \(BB(n)\) grows faster than any computational function, it may be proved. This number is defined as the maximum finite number of steps after which an \(n\)-state Turing machine terminates. The sum \(\sum_{n=1}^\infty 1/BB(n)\) over \(n\) is an incalculable real number as a consequence.
To partially summarize, these are interesting topics although – I believe – most of us have been exposed to computational complexity and artificial intelligence at various points and the most general impressions we get after a few hours arguably agree with what the experts believe (in this sense, the complexity science is a much less esoteric science than theoretical physics). It seems to me that these topics have very little to do with physics.
There's one point at which Aaronson may have tried to suggest that physics is relevant. He wrote that the black holes (and their singular spacetime geometry) could be used to construct computers whose speed doubles after every step and they could quickly calculate problems that require infinitely many steps etc. (The black holes were added as a "hope" to "sex his argument up".)
However, this is not the case. If such gadgets were possible in principle, the world could probably be shown to be inconsistent. Quite generally, the laws of physics tend to avoid such traps. So if you ask how the black holes may affect the speed of computation – I mean practical computations that the observers outside it may want to perform – their influence is exactly the opposite. They slow things down. Objects in a gravitational field display red shift, not blue shift, much like objects that are drifting away from us. This "prevalence" of red shift relatively to blue shift in physics is exactly what prevents moving computers from becoming too fast, from becoming the "NP-completeness oracles" or, using Aaronson's terminology when he was a student, "fairies". In most cases, physics has limitations that make the maximally efficient physical computer less efficient than the fastest design you could think of if you knew no physics.
This chapter also touches the question whether computer-assisted proofs may be counted as proofs. Well, I agree that people want to "feel" that they understand the reasons why something is true. A very large number of steps or tests that may only be done by a computer limit this "perceived direct contact with the truth".
At the same moment, I need to emphasize that this perception is subjective. And if someone doesn't "feel" a proof, it doesn't mean that the proof doesn't exist. After all, someone may "feel" it because he or she is a better mathematician. It's extremely important for people to understand that if they don't understand something, it may be just due to their personal limitations and not because there is something wrong with the thing they don't understand! Someone else may be smarter and understand it but even if there's no one like that in the world today, someone may emerge in the future who will understand it! The truth isn't the same thing as the subjective feelings of the truth; the latter are less eternal and less accurate and the former – the actual truth that is independent of individuals – should be considered superior.
Personally, if I may write down a program that verifies some steps that are needed to complete a proof (think about the Four Color Theorem as an example), I will believe the proof. A more direct proof that doesn't need a computer may be preferred. But let me admit, my motivation to search for such a computer-free proof diminishes rapidly once I know a proof that the statement is true – and I do count computer-assisted proofs among proofs. After all, I realize that computers are less likely to make well-defined particular errors than my brain because sharply cut silicon is more reliable than fuzzily connected proteins. In this sense, I believe the steps that were done by a computer more than I believe the steps that could have been plagued by a human error!
But anyway, the knowledge of the truth is far more important for me than the efficiency with which the truth may be reached or proved. Some important truths simply are just hard to find and hard to understand – and this is what actually makes them more important than the low-lying fruit-truths in average.
It seems to me that Scott Aaronson and others disagree about these points, too. In my opinion, they're victims of irrational emotions. Instead of looking for the cold hard truth, they may be looking for some emotions. As they're doing that, they may completely miss rather important meta-facts such as the fact that their brains are more likely to make errors in executing an algorithm than a silicon-based computer! And they may miss many other facts, too.
Complexity and P vs NP
Chapters 5 and 6 are dedicated to "Paleocomplexity" and "P probably isn't NP". These pieces of text are wonderful discussions about the scaling of the time and memory needed to solve various algorithmic problems. I have never been any professional expert, of course, but I got educated in this background many years ago. Aaronson wittily discusses many algorithms, their clever conversions to each other, and so on.
The problem promising you $1 million is the "P is or is not NP". Here, P are the problems that may be solved in polynomial time; NP are those whose solution may be verified in polynomial time. If the classes are equal, "P = NP", it means that every problem that can be "checked quickly" may also be "solved quickly". Because the finding of solutions looks "more creative" than their verification, people generally believe that "P is not NP" but a proof doesn't exist yet.
I am not so sure that "P is not NP", although I find it a bit more likely that the classes are not equal. However, if "P is NP" according to the definitions, it still doesn't imply that the procedures needed to solve a problem are really practical. The exponents in the power laws may be very large, and so on.
As a guy who's had some successes in math olympiads etc., I could have some probability – like many others – to solve similar problems, e.g. "P is or is not NP". However, the fame and perhaps the money is the only major motivation here for me, and it's too little. The reason why those things don't really excite me at the visceral level is that they're not really unique. They're elements in an infinitely tall power of ever more refined and complex mathematical claims that may wait for their resolution.
Imagine you prove that "P is not NP". But new problems are immediately waiting. One may divide the problems into finer classes and new sets and lots of new questions about their identity arise. Aaronson discusses many examples. In principle, this is a neverending sequence of questions. However, one can't really say that the more complex problems are negligibly important because they're qualitatively the same thing as the "P is not NP" question you decided to solve.
In physics, the search for a theory of everything is a much more unique and "terminal" process. And even some more modest goals in physics seem more unique and "terminal" than the problems in the complexity theory.
It's about complexity of problems as well as the differences (or equivalence) between human brains and artificial thinking machines.
When one reads this fun stuff, he may see how these complexity folks are thinking and – even if he knows the principles – he realizes which of them are considered important (and, in many cases, more important than they deserve) by the complexity theorists.
I would say that not even Aaronson would claim that this chapter has anything to do with physics but I have been surprised many times in my life so I am not certain.
Mathematical problems may be easy-to-solve or harder. We may order their difficulty in a way. Two problems may be equally (qualitatively) difficult. If one is harder than another, it means that an algorithm to solve the former implies the existence of an algorithm solving the latter but not the other way around. And so on. Are there intermediate difficulty problems between two known classes? You can imagine what he writes about.
A central thesis worshiped by these complexity theorists is the Church-Turing thesis: algorithmically solvable/calculable problems are exactly those that may be solved/calculated by a Turing machine – a particular structurally simplified model of a universal enough computer.
The complexity theorists including Aaronson are clearly impressed by this thesis. Your humble correspondent – and, I believe, most theoretical physicists – would decide that the thesis is mostly ill-defined or a vacuous tautology or potentially wrong, depending on the definition of "algorithmically solvable problems". The complexity theorists' obsession with the thesis and similar theses may be a part of the reason why they haven't done too much genuine progress in artificial intelligence and other things, as discussed below.
Their excitement isn't too difficult to understand. The key insight is that all intelligent enough thinking is in principle the same activity. Even if you have a different architecture of a microprocessor (80386, 6510, ARM...), you may still employ the chip to interpret a programming language. An interpreter of another programming language may be written in your preferred programming language which runs on any computer deserving the name; the task to write these interpreters is more or less straightforward. So all computers and languages may simulate each other so they're equally potent. To some extent, this must hold about differently thinking human brains, too.
It's great to realize this fact about the universality of computation but once we realize it, we should also realize it's vacuous.
(The Church-Turing thesis may be more than a vacuous statement but one would first have to give an exact definition to the "algorithmically calculable functions/problems" that don't refer to a particular machine. Clearly, this required definition will refer to some particular machine or some particular machines, and for different choices, the Church-Turing thesis may be both right or wrong. If you build the definition on Turing-equivalent machines, it will be right and vacuous. If you insert some other hypothetical machines, probably physically impossible ones, it may be wrong. Garbage in, garbage out. You don't learn anything.)
Physicists are also enthusiastic about similar equivalences of something – namely theories – but they only become elevated in the case when the equivalence is more surprising and nontrivial than a straightforward translation of a program from one programming language to another. When the equivalence between these theories is surprising and hard to prove, physicists call it a "duality". Exactly because it's not trivial, a duality is very potent. It seems to me that the complexity theorists never switch to the mode of thinking in which they call a spade a spade – in which they decide that a trivial insight is trivial – and that's why they sometimes remain stuck in the quagmire of trivial and vacuous insights.
After all, the chapter also mentions that Turing correctly predicted that the capacity and performance of the computers would grow by a huge (nearly realistic, it turned out) factor within 50 years. But he incorrectly predicted the rise of artificially intelligent machines that would become indistinguishable from humans.
Another idea that Aaronson's criticizes is "meat chauvinism", namely the assumption that thinking machines composed of proteins (a set that includes a majority of commenters on this blog) are more conscious or intelligent etc. than artificial machines etc. If a computer program simulates a human, it or he or she must be given the same status and "approved consciousness" and human rights, Aaronson thinks.
Well, I have mixed feelings about that. More precisely, I agree that 1) the inner functioning is a more essential part of an intelligent device and its "identity" than the precise nature of the transistors or cells or technical architecture, but 2) the clever computers clearly don't have to be given human rights. It's up to people or a society – at least as long as the people are in charge – whether they respect the human rights of such computers. As I have argued many times, science cannot answer moral questions.
The very usage of the word "chauvinism" shows that Aaronson is prejudiced in these matters – and his opinion differs from mine. This word "chauvinism" is arguably meant to sound negative – at least that's my conclusion after years in which extreme leftists were surprised when I felt proud after they identified me as a chauvinist of any sort. But let me tell you something: chauvinism is often a great and essential policy. For example, computers may be equivalent to humans in many respects but they're not equivalent in others and it's legitimate for me and every other voter or politician to consider the replacement of humans by computers undesirable. So from my viewpoint, it's right to "discriminate" against computers.
But I don't want to talk about these "political questions" only – even though the number of essays criticizing PC, egalitarianism, and similar junk ideologies is never high enough. The very idea that a smart enough computer could be "really equivalent to a human mind with all of its consciousness etc." could be wrong. In particular, if you create a classical simulation with a random generator that "behaves" indistinguishably from a quantum system, it could be fundamentally a different thing when it comes to its consciousness etc.
I am referring to the Conway-Kochen free will theorem. The randomness implied by quantum mechanics may be shown to arise locally in the very region where the value of an observable is decided for the first time – that's what is meant by the "free will" here. However, this property is violated if you supplement an artificial engine with an external random generator. In that case, the decisions are really made by this generator where a big part of the "identity" lies. And you don't want to give human rights to a random generator because it's just too dull. Again, science doesn't imply what the right policies are but because there is a fundamental feature in which the actual quantum object and its classical simulations are inequivalent, it's surely legitimate to treat them differently. (Every ideology claiming that A and B should be treated equally in situations C and D is based on the fact/claim that A and B are equivalent in some respects E, F while totally overlooking the fact that they're inequivalent in other respects G, H: it is always an example of an ideological cherry-picking.) I don't say it's desirable or necessary. It's just a sensible possibility that some people may prefer.
At the end of the chapter, the author solves a problem from the previous chapter. Spoilers follow. The \(n\)-th Busy Beaver number \(BB(n)\) grows faster than any computational function, it may be proved. This number is defined as the maximum finite number of steps after which an \(n\)-state Turing machine terminates. The sum \(\sum_{n=1}^\infty 1/BB(n)\) over \(n\) is an incalculable real number as a consequence.
To partially summarize, these are interesting topics although – I believe – most of us have been exposed to computational complexity and artificial intelligence at various points and the most general impressions we get after a few hours arguably agree with what the experts believe (in this sense, the complexity science is a much less esoteric science than theoretical physics). It seems to me that these topics have very little to do with physics.
There's one point at which Aaronson may have tried to suggest that physics is relevant. He wrote that the black holes (and their singular spacetime geometry) could be used to construct computers whose speed doubles after every step and they could quickly calculate problems that require infinitely many steps etc. (The black holes were added as a "hope" to "sex his argument up".)
However, this is not the case. If such gadgets were possible in principle, the world could probably be shown to be inconsistent. Quite generally, the laws of physics tend to avoid such traps. So if you ask how the black holes may affect the speed of computation – I mean practical computations that the observers outside it may want to perform – their influence is exactly the opposite. They slow things down. Objects in a gravitational field display red shift, not blue shift, much like objects that are drifting away from us. This "prevalence" of red shift relatively to blue shift in physics is exactly what prevents moving computers from becoming too fast, from becoming the "NP-completeness oracles" or, using Aaronson's terminology when he was a student, "fairies". In most cases, physics has limitations that make the maximally efficient physical computer less efficient than the fastest design you could think of if you knew no physics.
This chapter also touches the question whether computer-assisted proofs may be counted as proofs. Well, I agree that people want to "feel" that they understand the reasons why something is true. A very large number of steps or tests that may only be done by a computer limit this "perceived direct contact with the truth".
At the same moment, I need to emphasize that this perception is subjective. And if someone doesn't "feel" a proof, it doesn't mean that the proof doesn't exist. After all, someone may "feel" it because he or she is a better mathematician. It's extremely important for people to understand that if they don't understand something, it may be just due to their personal limitations and not because there is something wrong with the thing they don't understand! Someone else may be smarter and understand it but even if there's no one like that in the world today, someone may emerge in the future who will understand it! The truth isn't the same thing as the subjective feelings of the truth; the latter are less eternal and less accurate and the former – the actual truth that is independent of individuals – should be considered superior.
Personally, if I may write down a program that verifies some steps that are needed to complete a proof (think about the Four Color Theorem as an example), I will believe the proof. A more direct proof that doesn't need a computer may be preferred. But let me admit, my motivation to search for such a computer-free proof diminishes rapidly once I know a proof that the statement is true – and I do count computer-assisted proofs among proofs. After all, I realize that computers are less likely to make well-defined particular errors than my brain because sharply cut silicon is more reliable than fuzzily connected proteins. In this sense, I believe the steps that were done by a computer more than I believe the steps that could have been plagued by a human error!
But anyway, the knowledge of the truth is far more important for me than the efficiency with which the truth may be reached or proved. Some important truths simply are just hard to find and hard to understand – and this is what actually makes them more important than the low-lying fruit-truths in average.
It seems to me that Scott Aaronson and others disagree about these points, too. In my opinion, they're victims of irrational emotions. Instead of looking for the cold hard truth, they may be looking for some emotions. As they're doing that, they may completely miss rather important meta-facts such as the fact that their brains are more likely to make errors in executing an algorithm than a silicon-based computer! And they may miss many other facts, too.
Complexity and P vs NP
Chapters 5 and 6 are dedicated to "Paleocomplexity" and "P probably isn't NP". These pieces of text are wonderful discussions about the scaling of the time and memory needed to solve various algorithmic problems. I have never been any professional expert, of course, but I got educated in this background many years ago. Aaronson wittily discusses many algorithms, their clever conversions to each other, and so on.
The problem promising you $1 million is the "P is or is not NP". Here, P are the problems that may be solved in polynomial time; NP are those whose solution may be verified in polynomial time. If the classes are equal, "P = NP", it means that every problem that can be "checked quickly" may also be "solved quickly". Because the finding of solutions looks "more creative" than their verification, people generally believe that "P is not NP" but a proof doesn't exist yet.
I am not so sure that "P is not NP", although I find it a bit more likely that the classes are not equal. However, if "P is NP" according to the definitions, it still doesn't imply that the procedures needed to solve a problem are really practical. The exponents in the power laws may be very large, and so on.
As a guy who's had some successes in math olympiads etc., I could have some probability – like many others – to solve similar problems, e.g. "P is or is not NP". However, the fame and perhaps the money is the only major motivation here for me, and it's too little. The reason why those things don't really excite me at the visceral level is that they're not really unique. They're elements in an infinitely tall power of ever more refined and complex mathematical claims that may wait for their resolution.
Imagine you prove that "P is not NP". But new problems are immediately waiting. One may divide the problems into finer classes and new sets and lots of new questions about their identity arise. Aaronson discusses many examples. In principle, this is a neverending sequence of questions. However, one can't really say that the more complex problems are negligibly important because they're qualitatively the same thing as the "P is not NP" question you decided to solve.
In physics, the search for a theory of everything is a much more unique and "terminal" process. And even some more modest goals in physics seem more unique and "terminal" than the problems in the complexity theory.
Minds and machines
![Minds and machines]()
Reviewed by DAL
on
April 23, 2013
Rating:
No comments: