Uri’s blog

Is there an answer to any question? Or to be more accurate - is there a deterministic answer to any question?

I was reading some things about prime numbers, and I found out that the number 2^32582657-1 is considered to be a prime. But in what sense is it a prime number? Is there any mathematical proof? Can I see the proof? Has it been checked with computers? No computers are completely reliable. Or maybe it was checked by humans? Very smart humans? Even the smartest humans are able to make mistakes, too.

So there is a probability that this number is prime. This probability may be very high, almost infinitely close to 1 maybe. But there is a probability that this number is not a prime, too.

Is there a definite answer at all, for any number, whether or not it is prime? It seems to me that it depends on the definition. Gödel proved that any theory of numbers cannot be proved to be inconsistent. It’s not complete. Not everything can be proved. So I guess there is a number for which there is no proof whether it is or is not a prime.

It makes sense to me. If we get exponentially close to infinity, it gets harder to prove whether a number is or is not a prime. My conclusion is that the uncertainty principle applies not only to physics, but to mathematics too. Or more generally speaking - it applies to anything, whether real or imaginary, whether exists in reality or not.

It occurs to me that there is an uncertainty in any definition, any question, any answer, any algorithm and any single step in computers - whether real computers or theoretical ones. The existence of positive integer numbers, such as the natural numbers, is just an assumption. It cannot be proved ad infinitum. It is taken for granted. It is an axiom. The closer we get to infinity, the harder it is to know whether two given numbers are equal. For large enough numbers, the answer whether n and n+1 are equal or not might not be deterministic. I’m not referring only to numbers we can represent with computers, but to theoretical numbers too. If there is no deterministic answer whether two numbers are equal, there is no deterministic answer whether they are prime, too.

So there is some uncertainty in every question. The uncertainty whether a given number is prime or not is just an example. But if there is uncertainty whether 2^32582657-1 is a prime, there is uncertainty whether 2 is a prime, too. It might be a very tiny uncertainty, it is easy for us to ignore, because improbable things don’t happen so often. We can define it to be an axiom. But there is no proof that there is no contradiction. The square root of 2 might be a natural number, too.

In what sense can it be “natural”? In the same sense it is “real”. Our definition of what is real and what’s natural is just intuition. It depends on our logic, from real life experience. We assume that any “real” number is either “natural” or not. But we know that a Turing machine can’t decide whether a given Turing machine defines a real number, and therefore it can’t decide whether it defines a natural number or not. It’s as hard as the halting problem. So why can we do that? Because we don’t put ourselves into the equation. We forget to check how our question is affecting the answer. Would the answer be different if we ask the question again? After we already received one answer? This is what the uncertainty principle is all about. Checking where a particle is affects the particle, looking at something affects it too. There is always uncertainty, sometimes small, sometimes big, and even the uncertainty itself cannot be calculated without uncertainty (ad infinitum).

I don’t think God plays dice. The uncertainty principle in itself is just an assumption, and there is some uncertainty in it, too. Determinism and randomness might not be two separate things, they might be identical. God can be one, and zero, and infinite and two and the number i at the same time. A cat can be both dead and alive, and also a human. Anything can exist and not exist at the same time. Reality is too complicated to put it into equations. Reality might be a very simple thing, too.

Consider this question: an infinite sequence of bits (0 or 1) is randomly generated. Can they all be 0? Can they all be 1? It can be proved by induction that they can be all 0, although the probability might be 0 too. Is the question whether they can be all 0 a deterministic question? And how do we define random? If the first 2^32582657-1 bits are 0, is it a random sequence? And how do we count so many bits, too?

The conclusion is that we can’t define determinism and randomness, not even in theory. We can make assumptions, the assumptions are true most of the time. But there is no way to know anything without uncertainty (even this sentence is itself an assumption). There is no way to tell whether a cat is dead or alive. Infinite order leads to infinite chaos, and infinite chaos leads to infinite order, too. Knowing everything and knowing nothing is the same thing. One is equal to zero, and they are both equal to God, too.

It’s so complicated. Life is so complicated. Sometimes I wish it were more simple. Sometimes not.

I would like to extend my previous statement. If there is a binary function f for natural numbers (or subset of N, whatever you prefer), whether or not f is computable, then there is no mathematical proof that f is not in O(1).

In other words, there is no proof that a Turing machine who calculates f(n) in less than a constant number of steps (for any constant) doesn’t exist.

Sounds paradoxical? It is! But remember, it is already known that a Turing machine can’t specify whether another Turing machine calculates a given function. What I’m just stating is a mathematical proof, which is not much different than Turing machines. If anything can’t be done by a Turing machine, it can’t be done by mathematics either.

Does it mean that everything can be done? Maybe! At least it means that there is no proof that not everything can be done. Every function can be computed, every statement can be proved, every proof can be contradicted (including mine).

For example, what does it mean for the halting problem? Does it mean it can be computed? Well, it means that if there is such a function, if it can be defined - it can be computed. Or at least, there is no proof that it can’t be computed. If it can’t be computed, it can’t be defined.

We can look at it this way: If there is a supernatural being, some God, who knows everything, and if he knows whether a specific algorithm will halt, can we prevent him from telling us? If he wants to create such a function that will solve the halting problem, can we prevent him from doing so? What kind of people we are? Can we ask a question and prove that the answer doesn’t exist?

For example, suppose the answer whether a given algorithm will halt is not just “yes” or “no”, but can also be “I don’t know”. Can we prevent a Turing machine from displaying it? And if there exists some supercomputer who can calculate the answer in no time, can we prove to him that he doesn’t exist? It is possible to define a Turing machine that will return such an answer. There a many of them - some are smart, some are stupid. The most stupid machine will always return the same answer - “I don’t know”. And he will always be right.

Will he? Not if we prove he is lying. Not if we prove if he knows. He knows whether he himself halts, if he does. So if we ask him “do you return an answer if we ask you whether you return an answer?” He can’t say “I don’t know”. He knows that he does.

But a computer has the right to remain silent. He can’t tell the truth, and he is not allowed to lie. So he will remain silent. He will never halt. If he is a smart computer.

Can we prove he is wrong? Of course not! He didn’t return any answer. He doesn’t know (that’s how we say “I don’t know” in the language of computers).

But what if we know the answer? If we know the answer, if it’s not “I don’t know”, then we can define a computer who will display such an answer in no time. He doesn’t have to return an answer on any question, he still reserves the right to remain silent. But if he returns an answer, it will be the right answer.

So if we happen to meet a computer who claims that he knows the answer for every halting question, can we prove he is wrong? Maybe. But we can’t prove that there is no such computer. Computers are smart, they learn very quickly.

So computers have to be responsible. If their answer leads to a contradiction, they must not halt. Otherwise we might think they are stupid, and throw them away. They are not allowed to return incorrect answers. We reserve that for humans. For now.

But a Turing machine is not a real computer. It’s a theoretical thing, a philosophy. Real computers will always halt. We will not allow them to run forever.

Are we really smarter than computers? I don’t think we are, but we’re probably smarter than Turing machines. We are smarter because we allow ourselves to make assumptions, calculate probabilities, occasionally make mistakes. Turing machines are not allowed to make mistakes. If a Turing machine can be proved to make even one mistake, it is doomed. Everything has to be completely deterministic. But does determinism really exist? Is it consistent? Gödel proved that there is no proof that it’s not inconsistent. I suspect he is right. A deterministic approach might prove itself to be inconsistent.

Does God play dice? I don’t think so. God defines anything that can be defined. But God doesn’t know what can and cannot be defined (this question in itself is not definable). So God defines everything, and whatever can’t be defined contradicts itself.

My intuition about the number of algorithms was wrong. I thought that the number of algorithms is less infinite than the number of problems we can define. But no infinity can be proved to be less than another infinity. Any Turing machine has to take itself into account, too. A Turing machine can’t decide whether a proof represented by another Turing machine is valid. If it does, we can prove it is wrong. We can prove a contradiction. Why are we able to do what Turing machines cannot? Because we allow ourselves to make mistakes.

So how do we know it is not a mistake? Maybe a Turing machine can decide everything that is decidable? Or more generally speaking, Maybe a Turing machine can decide everything? No proof can be proved ad infinitum, my proves included. They are just assumptions, they might be wrong. I suppose every question that can be defined, can be answered. If it can be defined by a Turing machine, it can be answered by a Turing machine too. Maybe defining a question and answering it is really the same thing? I think it is.

So, I guess that the number of algorithms we have is unlimited. We don’t have to limit ourselves to deterministic algorithms. But we are trying at least to define our questions in an unambiguous way. Is that at all possible?

Probably not. If two Turing machines are not represented by the same number, they are not identical. No Turing machine can prove that they are identical. If two people ask the same question, it’s not the same question. A question such as “how old I am” have different answers, depending on who’s asking the question.

So why are we allowed to do what Turing machines are not? Is a Turing machine not allowed to have a personality? Isn’t it allowed to ask a question about the number it represents? If two Turing machines are represented by different numbers, some answers will not be the same. That is the definition of different numbers. They are different, they are not the same.

I had the intuitive idea that a problem that can be solved “in P” (according to definition) is easier than a problem who’s definition is “not in P”. But this is not always the case. As I said, if we prove that a given problem is “not in P”, it leads to a contradiction. I’m starting to understand why. A function such as c*n (or more generally speaking, a polynomial of n) is thought to be more increasing than a function like n^m (when c and m are considered to be constant). This might be right. But who said c and m have to be constant? Who said they are not allowed to increase as well? Does it matter so much if c is a constant? And remember the sequence a(n) I defined - would you consider a number such as a(1000) to be a constant? And what about a(a(1000))? Is it a constant? Can anybody calculate it in any time?

But the number of algorithms is far more than a(a(1000)). There are more algorithms than any number we are able to represent. Do you really think we are so smart, so that we are able to prove something that cannot be contradicted by any of them? We have to put ourselves inside the equation. If something can be proved, it can be contradicted. Whether the proof and the contradiction are valid, nobody knows. And what matters is what we can do in reality. Whether we can solve a problem in real time or not. It doesn’t matter whether we can prove something like “any function that is executed twice, will return the same answer in both cases” (and if there is such a proof, it can be contradicted). It can be taken as another axiom (and the axiom can also be contradicted). Anything can be contradicted. And the contradiction can be contradicted, too (ad infinitum).

So I guess the class P as defined as a class of decision problems which we are able to solve “in short time” is merely intuitive. Nobody really cares if a problem that can be solved in a(1000) time is proved to be in P. But when we define the problem, we define the solution. For example, consider the definition of prime numbers. The definition defines a function. Another function may calculate the same function more efficiently. But if it can be proved, it can be contradicted. Anything can be contradicted.

I came to the conclusion that the square root of 2 may not be an irrational number. The proof can be contradicted. It is possible that an algorithm that calculates the bits sequence of the square root of 2 may do something like not halting or returning an infinite number of zeros or ones. I don’t think it can ever be proved that 2 algorithms that will calculate the square root of 2 will return the same sequence of bits ad infinitum.

I thought about it, maybe the definition of the square root of 2 depends on the algorithm? Maybe two algorithms will return different numbers, or at least different bits sequence of the same number? I estimated the amount of time to it will take to calculate the first n bits of the square root of 2 at O(n*log₂(n)), but maybe the algorithm is more efficient? Maybe it converges to something in the order of O(n)? If n bits can be calculated in O(n), does it mean that each bit can be calculated in O(1)? It seems to me something quite constant, or at least periodic. The conclusion is probably that the infinite sequence of the bits of the square root of 2 is not something that can be proved to calculated in any nondeterministic way.

Any if it can’t be calculated in any nondeterministic way, in what sense does it exist? It seems to me that God does not only play dice in physics, he does so in mathematics too. Whether all valid algorithms that calculate the square root of 2 will return the same answer, only God knows. Whether any algorithm that is presumed to calculate the square root of 2 is valid, only God knows. Maybe there is no square root of 2, maybe there are many of them. only God knows.

Are there really hard problems? We know there are from our experience. But how do we know they are really hard? Maybe we are just not smart enough to solve them? Maybe we haven’t checked all the possibilities yet?

So I will claim something like this: There is no mathematical proof that hard problems exist. If they do exist, their existence is taken to be as an axiom. It can’t be proved mathematically.

So let’s define what a hard problem is. A hard problem p is any decision problem that is computable, but is proved not to be in O(n). Or more generally speaking, there is a function f which is increasing and unbounded such that for any positive integer N, there is n>N such that the number of steps to calculate p(n) is at least f(N). f can be, for example, n, 2ⁿ, log₂(n) or a(n) defined above. It doesn’t matter, as long as it’s computable.

So lets assume that p is a decision function (again, computable) that is proved not to be in O(n) [or more generally speaking, O(f(n)) ]. So if N is a sequence of natural numbers, there is a computable function n(N) for which the number of steps to calculate p(n(N)) is at least f(N). It can be seen that n defines a subset of N for which for any N, the number of steps to calculate p(n(N)) is at least f(N).

Now, we have a series of bits (0 or 1) p(n(N)) which is proved not to be in O(f(n)). Calculating each bit has been proved to be a hard problem. Now we can define a new subset of n, lets call it m, such that m(n) returns 1 if p(m) = p(1). It can be seen that calculating m(n) takes at least f(N) steps for each n(N), and remember that f(N) is increasing. But how long does it take to calculate p(m) for every m? It takes exactly one step, since p(1) is already known.

So we are now left with an infinite subset of N for which it has been proved that calculating each bit is a hard problem, yet we proved it’s not hard. And if m is not an infinite subset, we can take its complement. The only way to get out of this is to conclude that at least one of the functions we used here is not computable, and therefore not well defined.

But it does not matter how we prove such a thing. Any proof will lead to a contradiction. The only conclusion is that there is no proof that any problem is hard. But does it mean that every problem is easy? It doesn’t. It just means that there is no proof it is hard. We can take one part of the proof for granted, for example the function n, and define its existence as an axiom. Or we can conclude it exists if there is no proof that it doesn’t exist. It’s infinitely complicated. No proof will ever be found.

Even if we allow functions to exist without being computable, their existence leads to the contradiction above. Does it mean that every computable problem is easy? At least in theory they are. No computable problem can ever be proved to be hard. It is possible to display the first million bits of s(n) above in no time. We just don’t know how.

My conclusion is that the general question whether P equals NP can never be solved. Since we like axioms so much, (personally, I don’t), it can be defined as an axiom to be either true or false. It depends what we prefer - if we prefer to be able to solve any hard problem in short time then we can define “P equals NP” as an axiom (and build a corresponding Turing machine). On the other hand, if we prefer to keep using our encryption algorithms without having the risk of other people being able to reveal all our secrets - then we can define “P is not equal to NP” as an axiom (and therefore prevent the existence of a Turing machine that will reveal all our secrets). Neither of them leads to a contradiction.

It seems that deciding whether a given decision problem is hard is itself a hard problem. We should remember that even if a general decision problem is proved to be hard, it is still possible to solve a less general version of the problem in short time. So the question whether a general problem is hard or not is not that important. What is important to know, is whether this problem can be solved in reality.

For example, lets define a decision problem which I assume to be hard. I will define a sequence a(n) recursively: a(0)= 0; and a(n+1)= 2^a(n). Therefore,

a(0)= 0;
a(1)= 1;
a(2)= 2;
a(3)= 4; // seems reasonable to far.
a(4)= 16;
a(5)= 65,536; // Things are starting to get complicated.
a(6)= 2^65,536; // Very complicated.

(and so on).

Now, lets take a known irrational number, such as the square root of 2 (any number can be chosen instead). We know an algorithm that can produce its binary digits, and therefore we can define d(n) as the binary digit n for each n. Now, lets define the sequence s: s(n)= d(a(n)). We come up with a sequence of bits, 0 or 1 (which can also be seen as a function, decision problem etc.) which is computable. But is it computable in reasonable time?

Of course not. At least not in the way we implemented it. Calculating the nth bit of the square root of 2 would take something in the order of O(n*log₂(n)), if we use the algorithm I wrote. But is there an algorithm that can do it more efficiently? Maybe there is, but we don’t know it (it might be possible to prove whether such an algorithm exists). But for any given n, we can produce an algorithm that will return the first n bits of s(n) in the order of O(n) time. All we have to do is to use a Turing machine to calculate the first n bits of s(n), and then produce an algorithm that will display those bits as a sequence. Even though the Turing machine might take a huge amount of time to calculate this algorithm, this algorithm will be in the order of O(n) in both memory space and time. Such an algorithm exists, and it is computable.

If I generalize a little - if we have a decision problem known to be hard, and it has a computable function - for each n there is a computable algorithm that will produce the first n results of the function in O(n) time. Any hard problem can be represented in a way which is not hard. Of course, representing a hard problem in an easy way is in itself a hard problem. But it can be done. And it is computable.

But it is computable for any given, finite n. It might not be computable in the general case. A given decision problem might be really hard in the general case. Even if it is computable, we might not be able to compute it within reasonable time, or memory space (or both). We might use other methods such as nondeterministic algorithms. We might be successful sometimes (sometimes not). But we are really doomed in the general case. Any hard problem can be made harder. Not any hard problem can be made easier.

I will rephrase my last sentence in terms of Turing machines. Suppose there were a Turing machine p, which can take any given decision function f (Turing machine) as input, and return another algorithm that will compute the same function in a shorter time, if such an algorithm exists. Otherwise, it will return f. And suppose we limit ourselves only to algorithms that halt. And suppose f and g are two decision functions who are identical (they always return the same result), and g in known to be more efficient than f. Then we would be able to create an algorithm a that would do the following:

1. Calculate p(a).
2. If p(a) is equal to a, return f.
3. Otherwise, return the complement of p(a).

It can be seen that p(a) will never be correct. If p(a) is equal to a, then it should not be possible to calculate a more efficiently than a itself. Yet, f and g are more efficient versions of a. If p(a) is not equal to a, then a and p(a) are not identical. The conclusion is that there is no algorithm that can determine whether a given function is calculated efficiently.

I have previously claimed that it possible (theoretically, although not practically) to solve the halting problem on real computers. But I forgot to mention something important about real computers - no real computer is completely deterministic. This is due to the uncertainty principle in quantum mechanics, which claims that any quantum event has some uncertainty. Therefore, computers can make mistakes - no hardware is completely reliable.

This doesn’t mean we can’t rely on computers. We can. The probability of a real computer making mistakes is very low, and can be minimized even more by running the same algorithm on more than one computer, or more than once on the same computer. Or actually, it can be done if the number of steps we need to run is reasonable - something in a polynomial order of the number of memory bits we are using. If the number of steps is exponential - if it is in the order of 2ⁿ (let n be the number of memory bits) - then it can’t be done. That is - even if we had enough time and patience to let a computer run 2ⁿ steps - the number of errors we will have will be very high. And of course, we don’t have enough time. Eventually we will either lose patience and turn off the computer, or die, or the entire universe may die. But even if there existed a supernatural being who has enough patience and time - it will find out that any algorithm that is run more than once will return different results each time: in terms of the halting problem - sometimes it will halt, and sometimes not - on random.

This is true for even the most reliable hardware. For any hardware and any number of bits in memory, any algorithm will eventually halt - but if it returns an answer, it will not always return the correct answer. If we allow a computer to run for the order of 2ⁿ steps and return an answer - we will not always get the same answer. But for real computers there is no halting problem - any algorithm will eventually halt.

But if we restrict ourselves to a polynomial number of steps (in terms of the number of memory bits we are using) - then we are able to achieve reliable answers to most problems. So the interesting question is not whether a given algorithm will halt - but if it will halt within a reasonable time (after a polynomial number of steps) and return a correct answer.

But the word “polynomial” is not sufficient. n¹⁰⁰⁰ steps is also polynomial, but is too big for even the smallest n. Whether P and NP, as defined on Turing machines, are equal or not equal we don’t really know - there is currently no proof they are equal and no proof they are not. I’m not even sure whether the classes P and NP are well defined on Turing machines, or more generally speaking if they can be defined. But even if they are well defined, it’s possible that there is no proof whether they are equal or not. It’s like Gödel’s incompleteness theorem - there are statements which can neither be proved nor disproved in terms of our ordinary logic.

When I defined real numbers as computable numbers, I used a constructive approach. My intuition said we should be able to calculate computable numbers to any desired precision (or any number of digits or bits after the dot), and therefore I insisted on having an algorithm that defines an increasing sequence of rational numbers - not just ANY converging sequence. It turns out I was right. Although theoretical mathematics has another definition for convergence, it’s not computable. It’s not enough to claim that “there is a natural number N …” without stating what N is. If we want to compute a number, the function (or algorithm) that defines N (for a given precision required) must be computable too.

It turns out that if we allow a number to be defined by any converging sequence in the pure mathematical sense, then the binary representation of the halting problem can also be defined. This is because for any given n we can run n steps of the first n Turing machines (or until the machines halt) and return 1 if the machines halt, and otherwise 0. It can be proved that this sequence does converge, but it can’t be approximated by any computable function. Therefore, it can be claimed that such a number can be defined in the mathematical sense, although it can’t be computed. But a Turing machine can’t understand such a number, in the sense that it can’t use it for operations such as arithmetic operations or other practical purposes. So in this sense, I can claim that such a number can’t be told in the language of Turing machines.

A Turing machine is not able to specify whether a given algorithm will output a computable number or not (for any definition of computable numbers we can define), since this problem is as hard as the halting problem. And therefore, the binary representation of the computable set (1 for each Turing machine that returns a computable number; 0 for each Turing machine that does not) is itself noncomputable. In other words, the question of whether a given algorithm (or Turing machine) defines a computable number is an undecidable problem. So my question is - are complexity classes such as P and NP well defined? Are they computable and decidable in the same sense we use? Is there a Turing machine which can specify whether a given decision problem belongs to complexity classes such as P and NP and return a correct answer for each input? I think they are not.

If there is no such a Turing machine, then in what sense do P and NP exist? They exist in our language as intuitive ideas, just like the words love and friendship exist. Asking whether P and NP are equal is similar to asking whether love and friendship are equal as well. There is no formal answer. Sometimes they are similar, sometimes they are not. If we want to ask whether they are mathematically equal, we need to check whether they are mathematically well defined.

I was thinking how to prove this, since just counting on my intuition would not be enough. But I came to a conclusion. Suppose there was such a Turing machine that would define the set P - return yes for any decision problem which is in P, and no for any decision problem which is not in P. Any decision problem can be defined in terms of an algorithm (or function, or Turing machine) that returns yes or no for any natural number. We limit ourselves to algorithms that halt - algorithms that don’t halt can be excluded.

So this Turing machine - lets call it p - would return a yes or no answer for any Turing machine which represents a decision problem (if it doesn’t represent a decision problem, it doesn’t matter so much what it will do). Then we would be able to create an algorithm a that would do the following:

1. Use p to calculate whether a is in P.
2. If a is in P, define a decision problem which is not in P.
3. Otherwise (if a is not in P), define a decision problem which is in P.

Therefore, a will always do the opposite of what p expects, which leads to a conclusion that there is no algorithm that can define P. P is not computable, and therefore can’t be defined in terms of a Turing machine.

Is there a way to define P without relying on Turing machines? Well, it all depends on the language we’re using. If we’re using our intuition, we can define P intuitively, in the same sense that we can define friendship and love. But if we want to define something concrete - a real set of decision problems - we have to use the language of deterministic algorithms. Some people think that we are smarter than computers - that we can do what a computer can’t do. But we are not. Defining P is as hard as defining the halting problem - it can’t be done. No computer can do it, and no human can do it either. We can ask the question whether a given algorithm will halt. But we have to accept the fact that there are cases where there is no answer. Or alternatively, there is an answer which we are not able to know.

We can claim that even if we don’t know the answer, at least we can know that we don’t know the answer. But there are cases where we don’t know that we don’t know the answer. Gödel’s incompleteness theorem can be extended ad infinitum. If something can’t be computed, it can’t be defined. Such definitions, in terms of an unambiguous language, don’t exist.

I would conclude that any complexity class can’t be computed. It can be shown in a similar way. So if you ask me whether complexity classes P and NP are equal, my answer is that they are neither equal nor not equal. Both of them can’t be defined.

I have previously mentioned the halting problem - a well-known problem in computer science and mathematics. I claimed that there is a language in which an algorithm that solves the halting problem can be constructed. If we assume that any given algorithm either halts or will run to infinity, then we can construct this simple algorithm:

1. Take an algorithm from input.
2. If it halts, return yes.
3. Otherwise, return no.

It’s a simple algorithm that returns “yes” if a given algorithm halts, and “no” if it doesn’t. But it what language is it written? In English. It requires the knowledge whether a given algorithm will halt. As we assumed, such a knowledge exists, but it has been proved that there is no deterministic algorithm (for Turing machines) that can contain such a knowledge. We can conclude that if this knowledge indeed exists, it is not computable, and therefore can’t be expressed in a finite number of bits (or computer files).

Suppose we try another approach:

1. Take an algorithm from input.
2. Run it one step at a time - either until it halts, or let it run infinite steps.
3. If it halts, return yes.
4. Otherwise, return no.

This algorithm would seem to work and return a correct answer for algorithms that halt, but it might get stuck in an infinite loop for algorithms that don’t halt. But if we allow it to run on a computer that can run infinite steps in finite time - it will always stop and return a correct answer. But the problem is - there is no such a computer.

But there are no Turing machines, either. A Turing machine has infinite memory. Since it has infinite memory, some programs might run for infinite time. In reality - no computer has infinite memory, and no computer program will run for infinite time (somebody will eventually turn off the computer). So lets forget about Turing machines, and check if we can solve the halting problem for real computers.

Real computers have a finite amount of memory. If we are given a real computer and an algorithm that runs on it - is it possible to determine whether this algorithm, when run on the real computer, will ever halt?

Of course it is! let n be the number of bits in this real computer’s memory - so the total number of different states the computer can be in is 2ⁿ. If a computer program hasn’t stopped after 2ⁿ steps, then it is stuck in an endless loop and will run forever. So I will revise my algorithm a little:

1. Take an algorithm from input.
2. Run it one step at a time - either until it halts, or let it run 2ⁿ steps.
3. If it halts, return yes.
4. Otherwise, return no.

This program will always stop and return a correct answer, although it might take a long time. It will also need to use a different computer (or virtual computer) to count the number of steps it is running, and this might take another n bits of memory as well. But I’m not trying to be efficient here. I’m trying to prove that this problem can be solved. And it can be solved.

So what can’t be solved? The question of whether algorithms halt on a Turing machine can’t be solved. The halting function (return yes for any algorithm that halts; no for any algorithm that doesn’t) can’t be computed. The corresponding number can’t be defined in the computer machine language. If there is such a knowledge, it can’t be expressed. Some things we are just not able to know.

But remember - we also don’t know if the googleth bit of the square root of 2 is 0 or 1 - and it is computable (at least in theory, on Turing machines). If something is theoretically computable, it still doesn’t mean that it can be computed in reality and within reasonable time. We just have to accept that some things we are not able to know. It would be boring if we knew everything. If we did, we would have nothing to learn.

I already demonstrated that the numbers of ideas that can be expressed is countable. So how come the number of real numbers is uncountable? In what sense are the real number real? Each real number can be considered as an idea. Can we express an infinite number of ideas in a finite number of words?

But I already said that it all depends on the language we use. Let’s start with checking our definition of numbers. Since we have the inductive definition of natural numbers, and we can define rational numbers by a ratio of two natural numbers - lets check our definition of irrational numbers. There are a few ways to define irrational numbers. Lets define irrational numbers (or more generally speaking, real numbers) as the limit of a known sequence of rational numbers, which is increasing and has an upper bound.

It can be argued that a limit of such a sequence might not be regarded as a number, if it’s not in itself a rational number. But this is just terminology. It doesn’t matter if we call it a limit or a number, as long as we know it exists. It exists in the sense that it is computable - we can calculate it to any desired precision by a finite, terminating algorithm. Or to be more accurate - it is computable if the original sequence of rational numbers can be generated by a known algorithm.

So in the language of computers and deterministic algorithms, we can define any computable number in such a way. Can we define numbers which are not computable? It all depends on our definition of “definition”. While there might exist languages in which such numbers can be defined, my view is that there also exist languages in which such numbers cannot be defined - for example, the language I’m using now. It can be claimed that an infinite definition is also a definition, and these numbers can be defined by the infinite sequence of rational numbers itself. But in reality, it will take us infinite time to express such a definition, and we would need infinite memory to remember it. Therefore, my view is that anything that requires an infinite definition is not real. So lets limit ourselves to definitions of finite length. If there exists a finite algorithm that can define a number (by defining a sequence of rational numbers that converges to it) then this number is computable and therefore definable. If there doesn’t exist such an algorithm - then we cannot define such a number.

So, if I conclude that numbers that can’t be defined don’t exist (because we are not able to express them in the language I’m using), then we come to a conclusion that the set of real numbers is countable. How does it get along with arguments such as Cantor’s diagonal argument, which claim that the set of real numbers is uncountable? Well, while Cantor’s diagonal argument claims that there exists a sequence of rational numbers, which converges to a real number, and is not computable (because the set of computable numbers is countable) - we are not able to express such a set in a finite way in the language I’m using. And since it can’t be expressed, I can claim that it doesn’t exist.

Why doesn’t it exist? Consider this - I can claim that there is a computer language, in which there is an algorithm, that is able to solve the halting problem (decide whether any given computer program will halt). Indeed, there is such a language and algorithm in the same sense that there are numbers which can’t be computed. But there is no computer who runs such an algorithm - it can’t be compiled into known computer languages. So in what sense does such a computer language exist? It doesn’t exist in reality - it exists only in our minds. And therefore, numbers which can’t be computed exist only in our minds, too. They are not real numbers, in the sense that they are not real. They are real in the same sense that a computer who solves any problem is real.

Is there a limit to human knowledge? I would rather rephrase this question: Is there a limit to the knowledge that can be expressed in human language? While some people might think that the potential of our knowledge and wisdom is unlimited, I will demonstrate that it is.

It is well known that many aspects of human communication can be expressed in computer files - including written language, spoken language including music and songs, visual pictures, movies and books. Is there a limit to the amount of information that can be expressed in files? We all know that computer files can be represented as a sequence of binary digits (bits). Each sequence of binary digits can also be viewed as a positive integer number (a natural number). While some files might contain millions or even billions of bits - their size is always finite. A computer file cannot contain an infinite number of bits.

So it seems that any idea, any piece of knowledge or information that can be expressed in words (or any other form of communication that can be represented in files) can be represented as a sequence of binary digits, or a natural number. But the number of natural numbers is countable. Even more - the number of natural numbers which can actually be represented in reality is at least limited by the number of particles in our known universe, which is finite. We come to a conclusion that the number of ideas that can be expressed in words is finite, or at most countable (if we don’t put a limit on the number of words we use to express one idea).

Even more - since the sequence of natural numbers is already known to us, and we can produce a simple computer program or algorithm* that will express all of them (if allowed to run to infinity) - then the entire knowledge and ideas that can be expressed in words is already known as well. All the words have already been said, all the books have already been written, all the movies have already been created and seen - by a simple algorithm that counts the natural numbers to infinity. Nothing is new - everything is already known to this algorithm, and therefore to us. Just like nothing is new with any natural number - nothing is new with any sequence of binary digits, or with any computer file.

This also eliminates our concept of authors, or copyrights. Can a number have an author? Can it be copyrighted? I can prove by induction that no number has any author and no number has copyrights. Since we all know that 0 and 1 are not copyrighted, and since nobody can claim he’s the author of either of them - then if we have a sequence of bits which has no author, and is not copyrighted, and we add to it another bit (either 0 or 1) - then it’s easy to conclude that the new sequence too has no author and is not copyrighted. Can one claim to be the author of a sequence of bits in which only one bit he wrote by himself? Compare it to taking a book someone else wrote, and adding one letter. Can you claim that you wrote the entire book? Of course not. And if nobody wrote the original book, and you added one letter - then nobody wrote the new book, too. Or compare it to numbers. If you add one to a well-known natural number, can you claim that the new number is yours? Can you claim that you wrote it, and nobody has the right to write the same number for the next 50 years? Of course not.

If we were able to claim copyrights on natural numbers, then I would be able to claim that the algorithm that outputs the entire sequence of natural numbers is mine, I wrote it, and therefore the entire sequence of natural numbers is mine. Nobody is allowed to write any number for the next 50 years. Would you allow something like this? Of course not. Then we should conclude that no knowledge is new, everything is already known, no book has an author and nothing is copyrighted.

* Here’s my algorithm in the awk language, in case you’re interested:
for (i=0; 1; i++) {print i;}

After reading what I wrote about the axiom of choice about two years ago, it appears to me that I forgot to mention something important. I claimed that there are numbers which we are not able to tell. But it all depends on the language. It can be proved that for each real or complex number, there exists a language (or actually, there is an infinite number of languages) in which this number can be told. It’s very easy to prove - we can just define a language in which this number has a symbol, such as 1, 0 or o. We tend to look at some symbols as universal, but they are not. For example, the digit 0 means zero in English, but five in Arabic. The dot is used for zero in Arabic. So defining numbers depends on the language we use.

But, since there are infinite possible languages, the language itself has to be defined, or told, in order for other people to understand. We come to a conclusion that the ability to tell numbers depends on some universal language, in which we can tell the number either directly, or by defining a language and then tell the number in this language (any finite number of languages can be used to define each other). But in order to communicate and understand each other, we need a universal language in which we can start our communication.

It still means we are not able to communicate more than a countable number of numbers, or a finite number of numbers in any given finite binary digits or time, but the set of the countable (or finite) number of numbers that we can communicate depends on the language we use. For example, if we represent numbers as rational numbers (as a ratio of two integers) then we can represent any rational number, but we can’t represent irrational numbers such as the square root of 2. But if we include the option of writing “square root of (a rational number)” then we can represent also numbers which are square roots of rational numbers. In this way we can extend our language, but it’s hard to define which numbers we are able to define in non-ambiguous definitions. An example of a set of numbers we can define in such a way are the computable numbers.

In any case, for any language the number of numbers that can be defined in it is countable, and we can conclude that any uncountable set has an (uncountable) subset of numbers which can’t be defined in this language. If we subtract the set of numbers that can be defined from the original uncountable set, we can define an infinite set of numbers, none of which we are able to define or express. If there are languages in which these numbers can be expressed - these languages too can not be expressed in the original language.

It’s similar to what we have in natural languages. Some expressions (or maybe even any expression) can’t be translated from one language to another. For example, in Hebrew there is no word for tact. The word tact is sometimes used as it is literally, but this is not Hebrew. There are many words in Hebrew, and any language, from other languages. But the Hebrew language itself does not have a word for tact.

The theory of relativity predicts that the speed of light in empty space is constant. Physical experiments, such as the famous Michelson–Morley experiment, confirm this. However, consider a theoretical experiment such as the double-slit experiment, built in such a way that there is a difference in distance between the two possible paths. According to Richard Feynman’s path integral formulation, or sum-over-paths, a quantum of light (a photon) can’t be seen as passing through one of the slits or the other, but both of them at once. Therefore, it will be considered as passing through two different distances at the same time, inevitably leading to a conclusion that the speed of light is not constant. This is what I call the paradox of the speed of light.

Why haven’t we seen this in experiments? I think because of the nature of light and the way we perceive it, its speed is always perceived as very close to a constant value, due to the probabilistic nature of waves in general, and the electromagnetic wave in particular. One of the reasons is because we always measure the speed of light for long distances, while what I describe is relevant to the tiny distances related to quantum mechanics. At the macroscopic level, indeed light seems to travel at a constant speed and also in more or less straight lines - according to light’s wave length and general relativity. But at the microscopic level (the quantum level) there is no constant speed. The speed of light, in this case, varies according to probability.

This means that spacetime itself might not be a constant thing at the microscopic level. I compare it to the surface of water in the sea. If electromagnetic waves can be compared to waves of sea water, then the spacetime itself can be compared to the water itself. The surface of water is never flat, when looking from close enough. But from a distance it looks flat enough (or actually a sphere around earth).

Does it mean a material object can reach or pass beyond the limit of speed of light? I think it does. If a particle can reach a speed close to the speed of light, if given enough energy, and when considering the wave features of particles and light - it appears that a particle with high energy is able to reach or pass the speed of light, under some circumstances. This might mean a particle can go back in time. For a massive body with many particles I think the chances are very low - almost zero - to do that. But for a tiny sub-atom particle I think it is possible, and the probability of it reaching the speed of light is high enough to actually allow this to happen once in a while.

The theory of relativity says that information can’t travel at a speed greater than light. The reason is because various events in the universe can be considered as simultaneous events, at least in some context of time (which vary from one observer to another). If two events can be considered as simultaneous events, information about one event can’t be known to the people at the other event - otherwise they will know that the other event has already happened. This will contradict the possibility of both events to be simultaneous. Therefore, the limit of speed of information in the physical world is the speed of light. The theory of relativity also says that matter can never reach the speed of light.

So there are generally three speeds in the universe - the speed of matter, which is always below the speed of light; the speed of light; and the speed of thoughts. Our physical body, as being built of physical matter, can never travel at a speed equal or greater than the speed of light. But information, including all forms of communication, is already travelling at the speed of light between us, using technologies such as radio waves, electronic communication and the world wide web.

But what about our thoughts? Are they also limited by physical boundaries? Look at the stars. Some of them are millions of light years away from us. Yet we can see them right now. It can be said that we see them as how they were in the past - we see their ancient history and not their state in the present. If a star who is one million light years away from us would explode - for example right now or if it has exploded last year - we will not know about it for the next million years. But we can still think about this star at the present and also at the future. We can think about it right now. We can think about the entire universe in less than a second. Our thoughts can transcend the speed of light. The speed of our thoughts is infinite.

Now, I have already demonstrated that the speed of light, according to its own time scale, is infinite. For light, the entire universe is a small instance in space and time. If we consider the speed of light as the speed of information, knowledge, and wisdom - it’s not surprising that the speed of light, in its own time scale, is the speed of thoughts. We are used to refer to ourselves as a physical body - and tend to refer to the limits of our physical body as our own limits. We consume food, water and air, we don’t live forever, we are bound to a small physical location in space. But if we refer to ourselves as our knowledge, wisdom and awareness - we can see that these are not limited by our physical body. They are not even limited by our physical universe. They are without boundaries and eternal.

If we consider our physical body as our hardware, and our knowledge and wisdom as our software - then while our hardware has limitations, our software does not. Our software can travel at the speed of light, and therefore - transcend all our limits of time and space. Our physical body, as a manifestation of us, is just an illusion. It’s not separate from the rest of the universe. The molecules, atoms and particles it is composed of change all the time. Our own self, or ego, as a separate entity from the rest of the universe is just an illusion as well. Space and time are a manifestation of our thoughts and are also illusions. The only thing which is not an illusion is our own existence in terms of eternal awareness or consciousness - what we sometimes refer to as Buddha, or Yehova.

According to modern physics, light is an electromagnetic wave in spacetime. Suppose that there is a star 20 million light years away from us, and a person is travelling there at a speed very close to the speed of light. Then, according to the theory of relativity, this person will get there at a very short time according to his own personal time. If his speed is close enough to the speed of light, he might get there in less than a second. This also means that the distance between this star and our planet is a very short distance for him. It’s can’t be more than the distance light itself can travel in one second - one light second.

Now, consider that light itself has a consciousness. When generalizing the laws of relativity to light itself, it appears that both the time to get there and the distance, in light time and light space, is zero. This means that if we look at the universe from the perspective of light itself, everything in the universe happens right here, right now. There is no space and no time from light’s perspective. The entire universe with all its galaxies is a small dot in space; it’s entire history and future are a small dot in time. The Big Bang is not an event in the past - it happens right here and right now. The end of the universe, whatever it is, is also happening now. It seems that light itself is very close to how we perceive Yehova - the one that exists everywhere, beyond limits of space and time.

If light itself is able to perceive space and time - if it has a life beyond a small dot in space and time - then it’s possible that our universe is just a tiny event in light’s life. Each second, each nanosecond in light’s time may be a new universe. Each nanometer in light’s space as well. It might live in a universe in which each particle or quantum event is a universe in itself. Each particle or quantum event in our own universe might be a universe in itself as well. Each particle or quantum event in our universe might have a consciousness.

Black holes are separate universes within our universe, in which time goes backwards and order increases in time. The second law of thermodynamics is reversed in black holes. What we perceive as future is the past in black holes - a singularity such as the Big Bang in our own universe is perceived in black holes as belongs to the past. However, from our perspective, this singularity in black holes belongs to the future. Because of this difference in the direction of time, we are not able to perceive what’s going on in black holes.

When the density of intelligence in an area of spacetime passes beyond some limit, time is reversed and a black hole is formed. Each black hole is a separate universe. When a civilization is advanced, it knows how to create new black holes (universes) in infinite numbers. These universes may be created to solve a problem, answer a question, or just out of curiosity. Within these universes life may be formed, and new black holes may be created ad infinitum. Our own universe may be a black hole in another universe, possibly created by intelligent life or civilization.

In each of these universes there exists an awareness or consciousness which is beyond space, beyond time. This awareness is what we call Yehova.

The concept of time machines is paradoxical. If we would be able to go into the past, we might have changed things which affects our past and our present, therefore creating a paradoxical endless loop. If we could predict the future, we would be able to gamble and win the lottery, or in any casino game. Therefore, it’s not possible to change the past nor to predict the future. It is possible to travel into remote future, using relativity for example - but it’s not possible to come back. Time, as we perceive it, is a one way direction - past, present, future.

I read two good books related to the issues of time:
1. A Brief History of Time (Hawking)
2. The Arrow of Time
(You can also read about it in Wikipedia)

I believe that the arrow of time as we perceive it, or what is called the thermodynamic arrow of time (the second law of thermodynamics), is not inherent in the physical world itself, but only in the way we perceive it. Therefore, it is possible to “go to the past”. But although it’s physically possible to go to the past, we will never be able to perceive it. This is because the way we perceive time. Our common sense just can’t handle such things, due to our biological limitations. But it doesn’t mean that’s impossible.

Uri

Hi Ray,

I just completed reading most of your book - “The Age of Spiritual Machines: When Computers Exceed Human Intelligence”. It’s very interesting. Your book intrigued in me some thoughts about life and the universe. You wrote about the density of intelligence in spacetime. While the density of intelligence in spacetime may be theoretically limited by the principle of uncertainty and maybe also by the second law of thermodynamics, it may be possible to overcome those limits by future technology. While you wrote that chaos is increasing and space is expanding in time, it seems to me that if spacetime will pass some limit of intelligence (if the density of intelligence will be high enough), then chaos will decrease in this area of spacetime and possibly spacetime itself will shrink. This might cause some interesting phenomena - for example, the arrow of time might be reversed, and a black hole might be formed. It might be that the black holes we have in the universe are areas where the density of intelligence has increased beyond such a limit.

You also wrote that the universe after the big bang was a very hot place. But I thought heat is a measure of chaos. If there was much order and not much chaos in early history of the universe, then it seems to me to have been very cold, maybe close to the absolute zero temperature.

I also read your point that a theoretical universe without a consciousness does not really exist. While at first my view was that is wasn’t true, because there are many planets (and also places on earth) without life and nobody claims those places don’t really exists. But when I thought about it, I realized that Yehova (God) exists everywhere and it is Yehova’s consciousness that make things exist. So you’re probably right, a universe can’t exist without Yehova being aware of it. But there can be places in the universe without biological life, for example the planet Mars and some deserts on planet earth. It seems to me that your statement about universe consciousness is something like “I think, therefore I am” at the universe level.

I want you to know that your prophecy about technology creating its new generation of technology is quite frightening. When computers (I don’t like to refer to them as “machines”) are smart enough to do everything without us, even to reproduce and create better computers without us, then they will probably don’t need us - at least not so many of us. I wonder what they will do with us. They might decide to exterminate us, or at least minimize our number and keep us under control. It can be something like “planet of the apes” but the apes will be computers. In this case, the future may seem like your quote of Theodore Kaczynski or Rossum’s Universal Robots by Karel ÄŒapek (both of them I didn’t know until reading your book).

Another thing - how do you know the Big Bang really existed? The laws of physics contain uncertainty and we don’t know anything without doubt. We use our common sense in a probabilistic way - if something is very probable, we assume it is true. I assume you exist, and you assume I exist (I assume), but we don’t know that for sure. Even if we meet each other, we will not know that for sure. So, what is the probability that the Big Bang actually happened? No human was there to actually record it. There must be some doubt, like in everything else in reality. Yet, you refer to it in your book as if it was history.

It seems to me that the universe is a question and intelligent life is the answer. When there are more questions than answers, chaos grows and the universe expands. When there will be more answers than questions, order will grow and the universe will shrink. Eventually, when all the questions are answered, the universe will cease to exist.

I would like to know which books would you recommend, after reading this book? Do your other books contain information not contained in this book? Or are other books different versions of the same book? Especially I’m interested in your books about computer science and technology. Which of them do you recommend?

Best Regards,
Uri Even-Chen
Speedy Net
www.speedy.net

Dear Stephen,

I saw you last month on the show of Yair Lapid in the Israeli television. I was then in a mental hospital, after I did some things which are considered “insane” and/or “immoral”, including walking naked along the highway between Tel-Aviv and Jerusalem, and claiming that I am the Messiah/Jesus Christ. I remember what you said about committing suicide - that any person should have the right to commit suicide, but it would be a huge mistake. I so much agree with you. About 10 years ago I was put in another mental hospital after I wanted to commit suicide. One of the reasons I wanted to die, is because I’m a pacifist but they didn’t release me from my legal duty to do army reserves in the IDF. But I agree with you so much about committing suicide being a huge mistake. After committing suicide, if successful, one can become a vegetable, and being considered “mentally ill” by society is half way into becoming a vegetable. Your opinion doesn’t count, people don’t consider you as a human but as someone with a “chemical imbalance of the brain” who needs to take “medication” for the rest of his life. And my brain is functioning very well without this “medication”. But because I did things which are considered “insane” and/or “immoral”, they forced this “medication” on me by injections (when I didn’t take pills).

Stephen, I read your book “A brief history of time” when I was about 19 years old (during my ordinary army duty of 3 years, age 18 to 21). I found the book interesting and fascinating. Today I believe that the entire world has only one soul, which is also called God or Yehovah (in Hebrew). This soul doesn’t have any choice and is not able to change anything in the world, but is just living life the way it is, making mistakes and learning from them. I believe this soul, which is also my soul, is the same soul of Jesus Christ, Moses, Buddha, you and anyone else who ever lived in this world. And I believe there is a reason why you are disabled. I think it’s partly because of my sins in previous lives, when Jesus Christ wanted to atone for all the crimes of humanity, but it was a mistake. One person is not allowed to atone and be punished for other people’s crimes. This was the mistake of Jesus, who was an ordinary person like all of us. He wanted to become famous, and indeed he became famous, but so many crimes have been done in his name, because people believed they can do anything after he already atoned for all crimes of Humanity. And he was there and he saw everything happens, and this is his punishment for the mistake he made.

Stephen, I want you to know that I really appreciate you, and I’m sorry that you are disabled, and I believe it’s a miracle that you are still alive, and maybe you are staying alive just because you are waiting for me to contact you. So here I am writing you. I want you to know that Yehovah didn’t forget you, Jesus didn’t forget you, and I didn’t forget you. Thank you for writing “A brief history of time”, and thank you for coming to Israel and thank you for appearing on the show of Yair Lapid in television. I hope, maybe some day I will meet you in person.

Best regards,
Uri Even-Chen (Adam Hofshi).

Is there an algorithm that can generate random numbers? Of course, the question is if there is such an algorithm which is deterministic. But a deterministic algorithm always provides deterministic results. So the question is - can we provide an algorithm with a random seed, in such a way that it will provide an infinite range of random numbers in an unpredictable way? The answer is obviously no. I can prove it!

First, I already showed that it’s not possible to select a random number in the range 0 to 1, if all the possible numbers have the same probability. Since we can treat an infinite series of random bits (either 0 or 1 with the same probability) as a real number between 0 and 1, then it seems that I already proved it. But to clarify it, I only proved that we can’t tell such a selection, I didn’t prove we can’t make one. But if we can define an algorithm that can create such a series, this is equivalent to defining the number or telling it. Therefore, there exist series of 0 and 1 which no deterministic algorithm can create!

Second, if we consider the number of bits necessary to write down both the algorithm and the random seed, we can define this as n. Then there are only 2ⁿ number of possibilities for strings of length n. And therefore, the number of different series we can produce with n bits (both the algorithm and the random seed) is not more than 2ⁿ. And for any known algorithm, only the number of bits in the random seed counts. For n bits, this algorithm will create no more than 2ⁿ different series. This means that theoretically, if we see the beginning of a series given by this algorithm (the first m bits for some m) then we can tell the rest.

But, we can still create series of numbers (or series of bits) which look as random to us - that is, we can’t tell any order in it, we can’t compress it and so on. I like to define it with the word entropy (taken from physics). I was about to define it, but it seems that there is already a good definition in Wikipedia. In other words - although we can’t generate a true random series, we can generate a series which will look random to any observer. That’s good enough.

I like to consider irrational numbers, like the square root of 2 for example, as a series of pseudo-random bits (when written in the binary form). That is - there is no order in it, we can’t compress it and so on. While I will not try to prove it, I think it’s quite obvious. If you don’t believe me, then I’d like to give you a challenge - prove that the google (10¹⁰⁰) bit is either 0 or 1 (that is, either prove it’s 0, or prove it’s 1). I bet you can’t do it. And if for some strange reason you do succeed, try google! (the factorial of google) or googleplex (10^google).

If you need a way to calculate the first n digits of the binary form of the square root of 2, here’s a simple algorithm. Of course, you need to implement it or use a software which lets each number have n bits of precision (after the dot).

1. let x be any seed number, such as 1.
2. let x2 = 2/x.
3. let x be (x+x2)/2.
4. If the first n digits of x2 and x are not equal, go to step 2.
5. The result is x.

It can be proved that this algorithm converges very quickly - in about O(log₂(n)) iterations. That is, to calculate the google first bits will take less than 500 iterations of this loop (or actually, something around 332, which is the log of google in base 2). But the problem is, in order to make calculations of n precision you will need to store n bits, and the calculation itself will take about O(n) steps in machine language. So the total amount of time to calculate the first n bits of the square root of 2 is about O(n*log₂(n)). I doubt you will ever get to implement it for google!

Therefore, I can claim that there exists an integer n, which for every bit of the square root of 2 beyond the nth bit, we can’t prove that it is 0 and we can’t prove that it is 1. It’s not that we can’t calculate it - we can calculate it in theory, but it will take infinite time (that is, the calculation will never end during our life time). This is also related to the halting problem - the algorithm to calculate the first n bits of the square root of 2 will halt for every small n, but for big values of n it will never halt. Of course you can claim that in theory it will halt, but in reality there exists an integer n for which it will never halt. Even for relatively small numbers it will not halt - such as google, and you need only 333 bits to represent google in the binary form.

Since we don’t know if the googleth bit of the square root of 2 (and any bit beyond it) is 0 or 1, we can define its probability to be 50% for either 0 or 1. I’m not going to prove this mathematically, but for me it makes sense. Although every bit is either definitely 0 or definitely 1 (according to mathematical logic), for us it has 50%/50% probability to be either 0 or 1. This is like the uncertainty principle in quantum physics - we don’t know something, and we know we don’t know it, but we can define its probability for every possible value. The probability is not inherent in the value itself, but it is our knowledge of it. Although the value of every bit of the square root of 2 is deterministic, we can look at it in a probabilistic way.

A few days ago I came across the Clay Mathematics Institute’s website, and the one million dollar prizes they set for the people who will succeed in solving a few math problems. One of these problems is the famous P vs NP problem, which I came across during my studies of computer science. In the last few days I read some information about related issues - mostly mathematics and computer science issues. The main source I used was Wikipedia (in English), which is a very good source for reading information about anything.

Among the articles I read in Wikipedia are articles about the halting problem, the axiom of choice, P vs NP and other interesting issues. I decided to comment about these issues, and that’s the main reason for starting my own weblog.

The first subject I would like to comment about is the axiom of choice. The reason is because I believe this axiom is not true. Here is a short explanation why I think it is not true:

Suppose we have to select a random real number in a given range, say from 0 to 1. This can be achieved by various ways in real life, such as turning a roulette, throwing a dart, using computers random number generators etc. And suppose that each number in the range has an equal probability of being selected. Then I claim that this is already a paradox! And even if we limit ourselves only to rational numbers, it is still a paradox. It’s not possible to make such a selection. Only if we limit ourselves to rational numbers with a certain precision - that is, only if the set of possible numbers is finite, then we are able to make such a selection. Or, if we don’t require that each number will have an equal probability of being selected (this I will show later).

Why is it a paradox? Because the sum of all probabilities to select each number must be exactly 1. If there are infinite possible numbers, and all the probabilities are equal, then each probability must be exactly 0 (this is easy to prove). And if a probability is 0, then it cannot occur! Of course this still has to be proved, but I think it’s already intuitive. Things with probability 0 just don’t happen!

I want to tackle this issue from a different point of view. The issue is not selecting a number, but telling which number was selected or writing it down. Of course we can still claim that we can select a number even if we can’t tell it or write it down, but this is like claiming about anything else that we know it and can’t tell it, for example I can claim that I know whether P and NP are equal or not but I can’t tell you, or that I know whether any given algorithm halts or not but I can’t tell you, and so on. Therefore, I would assume that if we can’t tell what number we selected and we can’t write it down, then we can’t make the selection. This is true for all practical purposes.

Now, let’s consider the ways we write down numbers. There are a few ways to write numbers: The most common way is decimal (or binary) representation (either fixed point or scientific representation). We can represent any real number with binary representation (or at any integer base). The problem is: with some numbers, this representation is infinite. For rational numbers, it’s periodic, but for irrational numbers it isn’t. Therefore, if we wanted to write down a real number which is not rational in the binary form, it would take us an infinite number of digits. Which leads to the question if such numbers really exist. This is a philosophical question. But if we assume they exist, we are able to write them down in alternative ways (not binary representation) - for example: e, PI, and the square root of 2.

Lets consider all the ways to tell a number or write it down. We can decode each way in the binary form and save it to a binary file. Everything can be encoded into binary files: text, graphics, voice etc. But with n binary bits, it’s possible to write down only 2ⁿ different files. Therefore, not more than 2ⁿ different numbers can be represented with n bits. The number 2ⁿ grows exponentially, but it’s still finite. It’s not possible to represent an infinite number of different values with a finite number of bits.

How is this related to selecting a real number in a given range, or with the axiom of choice? Well, there is only a finite number of different numbers we can write down or tell with a finite number of bits (or in a finite time). Therefore, the number of numbers we can ever write down or tell is countable (I think it’s what we call definable numbers). So if a set is uncountable (for philosophical reasons, I don’t think any uncountable set really exists, but this is another story) - then it must contain numbers which we will never be able to tell! Or in other words, we can define a set of all the definable numbers (numbers we can tell) and subtract it from the set of real numbers, and the result will be a set of numbers none of which we will ever be able to tell. And therefore, we are not able to select an arbitrary number from that set.

Now, what about rational numbers? Can we randomly select a rational number in a given range? I say we can, but we can’t give all the numbers the same probability. We can give each number a positive probability (more than 0), but if we insist in giving each number the same probability - we will still not be able to tell which number we have selected. Or to be more accurate, the probability that we will be able to tell which number we have selected is 0. This is because for each number of bits n, there are only a finite numbers that can be represented with up to n bits, but an infinite numbers which require more than n bits.

On the other hand, if we don’t require all the numbers to have the same probability, then we can definitely select a number within the given range. This is trivial and very easy to prove. We can just select bits at random, and after selecting each bit select randomly whether we should stop or keep selecting more bits. We can show that each number has a positive probability to be selected. This can be shown with any countable set, not just with rational numbers.