Version 1.61
Recommended by J. F.:
Parts of these notes are based on Lawrence Snyder’s Fluency in Information Technology, Chapter 23.
Computers are fast, but are there limits to what they can do?
Moore’s law: the number of transisters on a computer chip doubles every two years.
Can they, will they be able to, think?
Naive thinkers extrapolate the growing memory capacity and speed of computers and say, they’ll be thinking better than humans in 2020. Of course, it’s not the size of the brain but its organization that matters: whales have larger brains than humans, yet they are not smarter (or not much).
Ray Kurzweil’s prediction is more sophisticated. Kurzweil realizes that brain size is not all, but still predicts that computers will surpass humans in power of thought in 20–30 years. His reason: we will be able to scan the human brain in enough detail to reverse engineer it, and use that organization for the computer (The Age of Spiritual Machines, 1999; see the interview in Snyder, pages 329–332). Well, when the time comes, we’ll know whether he was right.
Kurzweil also believes that when the time comes, rather than being surpassed by artificially intelligent computers, human beings will choose to be transformed as we implant more and more cyber-functionality into our bodies.
Programs that mimic the style of an artist or composer. (Hm: is mimic what a creative artist does?)
Can all computers do the same things?
The Universality Principle (firmly believed, not proved) is that all computers have the power to compute the same computations (the same functions), only some faster than others and some with more memory than others.
If we built a computer with a new hardware instruction, it would not really give it the capacity to compute anything new, because we could emulate the new instruction in software on computers that lacked the hardware instruction. They would just be slower.
Some problems require work proportional to n (n = problem size), e.g., capitalize every word in a list.
Some algorithms require time proportional to n2, e.g., simple sorting algorithms. These are slower. Compare n2 time with n = 100 and n = 1000.
Some algorithms require exponential time: work proportional to 2n. Morever, for some tasks, such as factoring large numbers, there is no known algorithm that can do the job in less than exponential time. Another such task is finding the shortest or least costly path between n locations, a very important problem in transportation planning. These problems are considered intractable, i.e., very hard, really too difficult to solve on a large scale even with the fastest of computers. Formally they are known as NP-complete problems.
We actually know a little about some things computers cannot do, no matter how fast and powerful they become, and no matter how much time they are allowed. Some well-defined problems simply cannot be solved by computing (i.e., some functions are not computable).
The halting problem is an example of a non-computable task. (Too bad, because if it were computable, we could have the computer check our program to detect infinite loops.)
First, we need to define the problem. The halts function is defined as
halts(P, I) = true if program P halts with input I, false otherwise.
Clearly, for every program P, for every input I, when program P runs with input I, either it eventually stops running (halts(P, I) is true), or it keeps going forever (halts(P, I) is false). So the function is well defined.
But is it computable? Alan Turing showed in 1936 that the halts function cannot be computed. Here’s a sketch of a proof (not rigorous, but it gives a sense of the nature of the problem):
Suppose that halts is computable. (We are assuming something that is false, and the strategy is to show that this leads to a contradiction, so we have to reject the assumption).
If halts is computable, then we could define this JavaScript function, in which the parameter P is some function:
var Q = function (P) {
if (halts(P, P))
while (true)
console.log("running");
else
console.log("OK");
};or in Scratch-like pseudocode
define function Q with input P
if program P halts with input P
then
forever
say "running"
else
say "OK"Now what would happen if we run the function call Q(Q)? That is, we run the Q function with the parameter P, which means that inside the function, the variable P refers to Q. That is, we are running Q as a program which takes itself, Q, as input.
There are two cases to consider:
halts(P, P) is true: in this case, Q runs an infinite loop, so it does not halt. But since P = Q, this means that if Q halts when its input is Q, it does not halt. Clearly, this is impossible.
halts(P, P) is false: in this case, Q prints a simple console.log message and halts. But since P = Q, this means that if Q does not halt when its input is Q, it halts. This is also impossible.
Since both cases lead to an impossibility, we have to reject the assumption that led to the contradiction. That assumption was that halts is a computable function. Therefore, we have to conclude that halts is not a computable function.
Just in case you are worried that there is something fishy about the program Q being input to itself, there’s really nothing at all weird about that. Compilers are programs that take programs as input, and it is possible for a compiler to compile itself. A compiler that is not able to compile itself is considered inferior, so when compiler developers get their compiler to such a good state that it can compile itself, they go out and have a party to celebrate.
On a very small scale, the world is very strange. Electrons and photons to not have definite location and speed, but are characterized by probabilities. For example, in the “two slit” experiment, photons passing through two slits form a characteristic wave interference pattern. When a single photon is emitted, the same pattern is formed — as though the photon had somehow passed through both slits at once.
In some sense the particle (photon or electron) is in many states at the same time. If the quantum state can store information in a form that can be processed computationally, it wouldlead to breathtakingly fast solutions of problems that are NP-complete — such as factoring large integers. That would provide an effective method of cracking public key encryption, which depends on the computational difficulty of factoring the products of very large prime numbers.
So we might have to weep for our loss of privacy.
Except that weird phenomena like quantum entanglement might provide even better solutions for secret communication. If two particles are entangled, when one of them is observed in a certain state, the other is found to be in a correlated state, even over long distances. There is communication without even transmitting through the intervening space. This is too weird for me!
Not only will we see computers becoming more powerful; we will see many more computers that are less powerful. Already they are in our automobile engines, washing machines, smart phones, DVD players — even in car keys. We’ve heard of Google Glass; the Apple Watch goes on sale online April 24, 2015. Maybe soon in your coffee cup, your shirt, your handkerchief, your pen, curtains for your window.