The famous P versus NP problem in advanced mathematics has all of the ingredients of a great puzzle:
1) It is a problem which is relatively easy to explain to a layman.
2) The best minds in the world have been stumped by it.
3) There is an alleged one million dollar prize for its solution: http://claymath.org/millennium/P_vs_NP/
4) It has an elegant three page solution: http://arxiv.org/abs/cs.CC/0607093
5) The solution to the P versus NP problem has philosophical and religious implications.
The P versus NP problem is a problem about why certain problems in mathematics seem so difficult to solve, yet once a solution is known, it is very easy to verify that it is indeed a true solution. For instance, take the following set of integers, {-40, 67, 37, -7, 89, 34, 23, 32, 9}. Is there a subset of this set for which the sum of its elements adds up to 131? Try to solve it. You will find that it is not an easy problem to solve, even though it is an easy problem to state and it is easy to verify that the subset {67, 37, -7, 34} is indeed a solution. This problem is called the SUBSET-SUM problem. Mathematicians do not know of any efficient way of solving this type of problem on a computer.
The P versus NP problem can be stated as:
"Is the reason why solving the SUBSET-SUM problem seems so difficult because the SUBSET-SUM problem is inherently difficult or is there some clever method for solving this problem efficiently that mathematicians just have not found yet?"
The answer to this question is that the SUBSET-SUM problem seems so difficult to solve because it actually is inherently difficult to solve, i.e., in the language of modern mathematics, P is not equal NP. There are, in fact, no computers powerful enough to solve this problem when the number of elements in the set is larger than 100.
What does all of this mean? It means that there is a whole class of mathematics problems which we have virtually no chance of solving even with the help of modern computers - yet if G-d were to give us the solution, we could immediately verify that G-d's solution is indeed the correct solution.
There is a secular humanistic idea that we humans have the ability to figure everything out on our own, to create a perfect society where everyone is happy, living in peace and harmony without any type of religion guiding our lives. The solution to the P versus NP problem shows us that this idea is not grounded in reality. P not equal to NP tells us that we human beings were not created to solve complicated problems; even the computers that we build are only able to efficiently solve a limited class of problems.
We humans were only created to be able to understand the solutions to complicated problems, but not to solve the complicated problems. And this is why we are commanded to learn Torah, which has the answers to life's important questions, and why we were never expected try to figure these answers out on our own and succeed.
Thursday, December 2, 2010
Monday, June 8, 2009
The 3n+1 Phenomenon
Here is an interesting experiment: Pick any number. If it is odd, then multiply it by three and add one. If it is even, then divide it by two. Repeat this procedure until you obtain one and then stop. For instance, if you had picked the number 7, you would have obtained 3x7+1=22, 22/2=11, 11x3+1=34, 34/2=17, 17x3+1=52, 52/2=26, 26/2=13, 13x3+1=40, 40/2=20, 20/2=10, 10/2=5, 3x5+1=16, 16/2=8, 8/2=4, 4/2=2, 2/2=1.
Computers have verified that such a procedure will stop at one for all numbers up to about 4.79 x 10^17 - see the website http://www.ericr.nl/wondrous/index.html. But no one knows for certain that this procedure will stop at one for all numbers. And no one will ever be certain. Why?
Because in order to be certain of such, it is necessary to test the procedure out on all numbers. And since there are infinitely many numbers, doing such must take an infinite amount of time. Since we humans are finite beings, we don't have an infinite amount of time, so if the procedure always halts at one, we can never know this with absolute certainty - only G-d can know this. (For a rigorous mathematical proof of this fact, see http://arxiv.org/abs/math.GM/0312309.)
So this famous mathematics problem, which is known as the 3n+1 problem, is a great illustration of our limitations as human beings to comprehend our universe - it is a problem that is so simple that even a second grader can comprehend it, yet so complex that all of the mathematicians in the world will never be able to prove deductively that the procedure will always stop at one.
According to the ancient Greek humanistic view of the world, reason and logic are what make the world go around. According to the Jewish Torah view of the world, G-d is what makes the world go around. The 3n+1 problem demonstrates to us all that if the 3n+1 procedure stops at one for all possible numbers, then it is not because reason and logic dictate that it must do such; it is because G-d, Who created mathematics, decided that the 3n+1 procedure must stop at one for all possible numbers. From this simple mathematics problem, we all can see clearly how the ancient Greek humanistic view of the world is seriously flawed.
Computers have verified that such a procedure will stop at one for all numbers up to about 4.79 x 10^17 - see the website http://www.ericr.nl/wondrous/index.html. But no one knows for certain that this procedure will stop at one for all numbers. And no one will ever be certain. Why?
Because in order to be certain of such, it is necessary to test the procedure out on all numbers. And since there are infinitely many numbers, doing such must take an infinite amount of time. Since we humans are finite beings, we don't have an infinite amount of time, so if the procedure always halts at one, we can never know this with absolute certainty - only G-d can know this. (For a rigorous mathematical proof of this fact, see http://arxiv.org/abs/math.GM/0312309.)
So this famous mathematics problem, which is known as the 3n+1 problem, is a great illustration of our limitations as human beings to comprehend our universe - it is a problem that is so simple that even a second grader can comprehend it, yet so complex that all of the mathematicians in the world will never be able to prove deductively that the procedure will always stop at one.
According to the ancient Greek humanistic view of the world, reason and logic are what make the world go around. According to the Jewish Torah view of the world, G-d is what makes the world go around. The 3n+1 problem demonstrates to us all that if the 3n+1 procedure stops at one for all possible numbers, then it is not because reason and logic dictate that it must do such; it is because G-d, Who created mathematics, decided that the 3n+1 procedure must stop at one for all possible numbers. From this simple mathematics problem, we all can see clearly how the ancient Greek humanistic view of the world is seriously flawed.
The Primary Difference Between a Yeshiva Education and a University Education
Having had the privilege of studying in both a university and a yeshiva, I have observed the following:
In general, when a rabbi reads something that he does not understand, the rabbi will say, "I don't understand it."
In general, when a professor reads something that he or she does not understand, the professor will say, "It's nonsense."
In general, when a rabbi reads something that he does not understand, the rabbi will say, "I don't understand it."
In general, when a professor reads something that he or she does not understand, the professor will say, "It's nonsense."
The Geography of Thought
I recently read a book called The Geography of Thought by Richard E. Nisbett which has had a profound impact on the way I understand Torah. The subject of this book is how Westerners and Asians think differently. Consider the following fundamental laws of Aristotelian logic:
1) Law of Identity - If a statement is true, then it is true.
2) Law of Non-Contradiction - No statement can be both true and false.
3) Law of the Excluded Middle - All statements are either true or false.
These laws form a basis for Western critical thinking. As Westerners, it is difficult for us to even imagine a system of reasoning that is different from the Aristotelian system, but surprisingly there is a system of reasoning which is the exact opposite of the Aristotelian system:
1) Principle of Change - Reality is a process; it does not stand still and is in constant flux. Because reality is dynamic and flexible, concepts that reflect reality are also active, changeable, and subjective.
2) Principle of Contradiction - Reality, particularly the reality of life, is not precise and cut-and-dried, but rather, complex and full of contradiction.
3) Principle of Holism - In reality, as well as in human life, nothing is isolated and independent; rather, everything is relational and connected.
The Principle of Change is in direct contradiction with the Law of Identity in that according to the Principle of Change, the truth or falsehood of a statement is not static; if in one moment a statement is true, then in the next moment that same statement can be false. The Principle of Contradiction is in direct contradiction with the Law of Non-Contradiction, by definition. And the Principle of Holism is in direct contradiction with the Law of the Excluded Middle, since in a relational and connected world, the truth or falsehood of a statement may depend on its context.
These three principles form a basis for Eastern thought, according to Nisbett. Nisbett calls this system of logic "dialectical", and he mostly concentrates on Asian countries in the Far East like China, Japan, and Korea in his book; however, anyone who learns Talmud can see that the logic of the Torah is more in line with Asian dialectical logic than with Western logic. And this is really no surprise, since the Land of Israel is in Asia, not Europe. According to the Abarbanel, Noach's three sons Shem, Cham, and Japeth each inherited the three continents, Asia, Africa, and Europe, respectively. We Jews are descendents of Shem, who inherited Asia, not Japeth, who inherited Europe and gave birth to Yavan, the father of the Greek nation. So it is only natural that Asian dialectical logic conforms more to Torah than Western Greek logic does.
Therefore, Western Jews like myself who grew up in a society in which Greek Aristotelian logic is king and Eastern logic is considered at the very least nonsense and at the very most "mystical" need to understand that if one is to comprehend the Torah deeply, then one must throw away all preconceived notions that the Torah can be completely understood in terms of Western Aristotelian logic.
1) Law of Identity - If a statement is true, then it is true.
2) Law of Non-Contradiction - No statement can be both true and false.
3) Law of the Excluded Middle - All statements are either true or false.
These laws form a basis for Western critical thinking. As Westerners, it is difficult for us to even imagine a system of reasoning that is different from the Aristotelian system, but surprisingly there is a system of reasoning which is the exact opposite of the Aristotelian system:
1) Principle of Change - Reality is a process; it does not stand still and is in constant flux. Because reality is dynamic and flexible, concepts that reflect reality are also active, changeable, and subjective.
2) Principle of Contradiction - Reality, particularly the reality of life, is not precise and cut-and-dried, but rather, complex and full of contradiction.
3) Principle of Holism - In reality, as well as in human life, nothing is isolated and independent; rather, everything is relational and connected.
The Principle of Change is in direct contradiction with the Law of Identity in that according to the Principle of Change, the truth or falsehood of a statement is not static; if in one moment a statement is true, then in the next moment that same statement can be false. The Principle of Contradiction is in direct contradiction with the Law of Non-Contradiction, by definition. And the Principle of Holism is in direct contradiction with the Law of the Excluded Middle, since in a relational and connected world, the truth or falsehood of a statement may depend on its context.
These three principles form a basis for Eastern thought, according to Nisbett. Nisbett calls this system of logic "dialectical", and he mostly concentrates on Asian countries in the Far East like China, Japan, and Korea in his book; however, anyone who learns Talmud can see that the logic of the Torah is more in line with Asian dialectical logic than with Western logic. And this is really no surprise, since the Land of Israel is in Asia, not Europe. According to the Abarbanel, Noach's three sons Shem, Cham, and Japeth each inherited the three continents, Asia, Africa, and Europe, respectively. We Jews are descendents of Shem, who inherited Asia, not Japeth, who inherited Europe and gave birth to Yavan, the father of the Greek nation. So it is only natural that Asian dialectical logic conforms more to Torah than Western Greek logic does.
Therefore, Western Jews like myself who grew up in a society in which Greek Aristotelian logic is king and Eastern logic is considered at the very least nonsense and at the very most "mystical" need to understand that if one is to comprehend the Torah deeply, then one must throw away all preconceived notions that the Torah can be completely understood in terms of Western Aristotelian logic.
The Prisoner's Dilemma and Morality
Consider the following description of the "Prisoner's Dilemma", taken from Wikipedia:
Two suspects, A and B, are arrested by the police. The police have insufficient evidence for a conviction, and, having separated both prisoners, visit each of them to offer the same deal: if one testifies for the prosecution against the other and the other remains silent, the betrayer goes free and the silent accomplice receives the full 10-year sentence. If both stay silent, both prisoners are sentenced to only six months in jail for a minor charge. If each betrays the other, each receives a two-year sentence. Each prisoner must make the choice of whether to betray the other or to remain silent. However, neither prisoner knows for sure what choice the other prisoner will make. So this dilemma poses the question: How should the prisoners act?
The dilemma arises when one assumes that both prisoners only care about minimizing their own jail terms. Each prisoner has two options: to cooperate with his accomplice and stay quiet, or to defect from their implied pact and betray his accomplice in return for a lighter sentence. The outcome of each choice depends on the choice of the accomplice, but each prisoner must choose without knowing what his accomplice has chosen to do.
Let's assume the protagonist prisoner is working out his best move. If his partner stays quiet, his best move is to betray as he then walks free instead of receiving the minor sentence. If his partner betrays, his best move is still to betray, as by doing it he receives a relatively lesser sentence than staying silent. At the same time, the other prisoner's thinking would also have arrived at the same conclusion and would therefore also betray.
If reasoned from the perspective of the optimal outcome for the group (of two prisoners), the correct choice would be for both prisoners to cooperate with each other, as this would reduce the total jail time served by the group to one year total. Any other decision would be worse for the two prisoners considered together. When the prisoners both betray each other, each prisoner achieves a worse outcome than if they had cooperated.
There is a myth in the modern secular Western World that it is in the best interest of all people to be moral not because G-d commands us to be moral but because it is logical to be moral. In order to debunk this myth, let us examine the Prisoner's Dilemma: It is demonstrated above by pure logic that the rational choice for both prisoners to make is to betray each other, since betrayal always wins less jail time than silence, regardless of what the other prisoner does. Yet, if it were known to both prisoners that they were both innocent, then the moral choice would certainly be for both of the prisoners to remain silent. Therefore, it is not always logical to be moral, even if everyone would be better off if everyone were moral than if everyone were immoral! The truth of the matter is that the only reason for us to be moral is because G-d commands us to be moral.
Two suspects, A and B, are arrested by the police. The police have insufficient evidence for a conviction, and, having separated both prisoners, visit each of them to offer the same deal: if one testifies for the prosecution against the other and the other remains silent, the betrayer goes free and the silent accomplice receives the full 10-year sentence. If both stay silent, both prisoners are sentenced to only six months in jail for a minor charge. If each betrays the other, each receives a two-year sentence. Each prisoner must make the choice of whether to betray the other or to remain silent. However, neither prisoner knows for sure what choice the other prisoner will make. So this dilemma poses the question: How should the prisoners act?
The dilemma arises when one assumes that both prisoners only care about minimizing their own jail terms. Each prisoner has two options: to cooperate with his accomplice and stay quiet, or to defect from their implied pact and betray his accomplice in return for a lighter sentence. The outcome of each choice depends on the choice of the accomplice, but each prisoner must choose without knowing what his accomplice has chosen to do.
Let's assume the protagonist prisoner is working out his best move. If his partner stays quiet, his best move is to betray as he then walks free instead of receiving the minor sentence. If his partner betrays, his best move is still to betray, as by doing it he receives a relatively lesser sentence than staying silent. At the same time, the other prisoner's thinking would also have arrived at the same conclusion and would therefore also betray.
If reasoned from the perspective of the optimal outcome for the group (of two prisoners), the correct choice would be for both prisoners to cooperate with each other, as this would reduce the total jail time served by the group to one year total. Any other decision would be worse for the two prisoners considered together. When the prisoners both betray each other, each prisoner achieves a worse outcome than if they had cooperated.
There is a myth in the modern secular Western World that it is in the best interest of all people to be moral not because G-d commands us to be moral but because it is logical to be moral. In order to debunk this myth, let us examine the Prisoner's Dilemma: It is demonstrated above by pure logic that the rational choice for both prisoners to make is to betray each other, since betrayal always wins less jail time than silence, regardless of what the other prisoner does. Yet, if it were known to both prisoners that they were both innocent, then the moral choice would certainly be for both of the prisoners to remain silent. Therefore, it is not always logical to be moral, even if everyone would be better off if everyone were moral than if everyone were immoral! The truth of the matter is that the only reason for us to be moral is because G-d commands us to be moral.
A Story Written by Israel Schlaffer z"l
The following story entitled "A Terrible Incident" was written in the 1930's by my grandfather, Israel Schlaffer, to his children:
Dear Children, I wish to relate to you an incident. It happened thirty years ago on the day of Lag Baomer in a little town in Russia.
In those days I was still a little boy like you now. I studied in Cheder the whole day from morning to evening. I had no spare time except Shabbos and holidays and even then I had to go to Shule with my father in the morning and evening, and in the afternoon the teacher used to come to our house to examine me so that my father could see what I studied the whole week.
But one day of the year was distinct, --outstanding in our lives. That was Lag Baomer. That day we were free from studies and we could play and run around in the woods and in the fields out of the city.
On one Lag Baomer day, the day that this incident occurred we gathered in front of our teacher's house. We were all armed with bows and arrows. We lined up and we went to the woods with the teacher. There we had a good time and we enjoyed ourselves the whole day. Then the command came, "Home."
Another boy and I decided to remain here in order to play some more. We sneaked out from the line and we remained alone in the woods. The sun set, some stars already appeared in the sky -- it was a beautiful evening. Suddenly we heard beautiful music that attracted our attention. We followed the sound of the music because we wanted to see the man who sang so beautifully. And, behold, we stood before a house at the end of the woods. We wanted to see through the window who was singing inside. But we didn't see anyone. All we saw was a round box from which the sound came out. We became terribly frightened and with all our strength we started to run away from this terrible place. We thought that devils were mocking us. Really, how is it possible that a box should produce such charming and wonderful music?
This, children, was the first victorola that was brought to our town and we never heard about it and never saw it before.
Dear Children, I wish to relate to you an incident. It happened thirty years ago on the day of Lag Baomer in a little town in Russia.
In those days I was still a little boy like you now. I studied in Cheder the whole day from morning to evening. I had no spare time except Shabbos and holidays and even then I had to go to Shule with my father in the morning and evening, and in the afternoon the teacher used to come to our house to examine me so that my father could see what I studied the whole week.
But one day of the year was distinct, --outstanding in our lives. That was Lag Baomer. That day we were free from studies and we could play and run around in the woods and in the fields out of the city.
On one Lag Baomer day, the day that this incident occurred we gathered in front of our teacher's house. We were all armed with bows and arrows. We lined up and we went to the woods with the teacher. There we had a good time and we enjoyed ourselves the whole day. Then the command came, "Home."
Another boy and I decided to remain here in order to play some more. We sneaked out from the line and we remained alone in the woods. The sun set, some stars already appeared in the sky -- it was a beautiful evening. Suddenly we heard beautiful music that attracted our attention. We followed the sound of the music because we wanted to see the man who sang so beautifully. And, behold, we stood before a house at the end of the woods. We wanted to see through the window who was singing inside. But we didn't see anyone. All we saw was a round box from which the sound came out. We became terribly frightened and with all our strength we started to run away from this terrible place. We thought that devils were mocking us. Really, how is it possible that a box should produce such charming and wonderful music?
This, children, was the first victorola that was brought to our town and we never heard about it and never saw it before.
Why Did Adam HaRishon eat from the Tree of Knowledge?
We can understand why Adam HaRishon chose to eat from the Tree of Knowledge of Good and Evil through the following parable:
"Little Billy's father decided to teach his son all about electricity and magnetism so that Billy could learn physics. First, Billy's father taught Billy how electric motors work. He told Billy to never touch an exposed wire in an electrical circuit with a high voltage because if Billy did so, then Billy would get electrocuted and die. Billy was so fascinated with electricity and magnetism that he wanted to make his father proud and become a great physicist. Billy wanted to better understand the curious phenomenon of electrocution to advance his studies in physics, so he decided to electrocute himself. As a result, Billy died as the world's leading expert in the phenomenon of electrocution."
Similar to Billy's decision to electrocute himself, Adam HaRishon decided to eat from the Tree of Knowledge of Good and Evil so that he could make G-d proud by becoming the world's expert in the phenomenon of good and evil.
"Little Billy's father decided to teach his son all about electricity and magnetism so that Billy could learn physics. First, Billy's father taught Billy how electric motors work. He told Billy to never touch an exposed wire in an electrical circuit with a high voltage because if Billy did so, then Billy would get electrocuted and die. Billy was so fascinated with electricity and magnetism that he wanted to make his father proud and become a great physicist. Billy wanted to better understand the curious phenomenon of electrocution to advance his studies in physics, so he decided to electrocute himself. As a result, Billy died as the world's leading expert in the phenomenon of electrocution."
Similar to Billy's decision to electrocute himself, Adam HaRishon decided to eat from the Tree of Knowledge of Good and Evil so that he could make G-d proud by becoming the world's expert in the phenomenon of good and evil.
Subscribe to:
Posts (Atom)