Skip to comments.Quantum Leaps May Solve Impossible Problems
Posted on 10/10/2002 11:58:04 AM PDT by sourcery
"It is widely accepted now that, without a doubt, information is physical and quantum physics provides the rules of that physical behavior," George Mason University computer science professor Richard Gomez told NewsFactor.
Alan Turing might be considered the "John Forbes Nash of computer science" -- a troubled young Princeton genius who achieved prominence in the 1950s. Turing published one of the top 10 papers in all of 20th-century science -- "On the Computability of Numbers."
He killed himself over a conviction for homosexuality at the height of his genius, but since his death, his definition of "computability" has stood untouched and unchanged.
Now, however, Australian mathematician Tien Kieu has made a discovery that could turn the last century of mathematics and all of computer science on its head: Problems that used to be considered "unsolvable" or "incomputable" may be solved using the almost mystical properties of quantum mechanics.
A Tour of Turing Computers
Computability has long been defined by the so-called "Turing-Church Thesis," named for the 20th century's two giants of computer science and mathematical logic, Alonzo Church and Alan Turing, who essentially invented the modern-day computer.
The Turing-Church Thesis says that if you have a problem that can be solved using a set of well-defined rules in a finite number of steps, then you have the equivalent of a problem that can be solved using a computer program. In the earliest days of computer science, a program was known as a "Turing Machine" -- a generalized representation of computer software.
"Problem solvability" has been equated ever since with "Turing computability." If a computer (Turing Machine) cannot solve a problem, the problem cannot be solved, and vice-versa -- if you have an insoluble problem, a computer will not be able to solve it!
Turning Turing on His Head
No one has yet produced a knockout argument to show otherwise -- until now, according to Kieu.
"We dispute the Turing-Church thesis by showing that there exist computable functions -- computable by executing well-defined quantum mechanical procedures in a finite manner -- that are not Turing-computable," Kieu claims in a recent paper on the topic. In other words, Kieu claims to have discovered incomputable problems that are actually computable with the help of quantum mechanics.
"I have read Tien Kieu's papers and found them to be consistent with findings of other researchers in the area of quantum computation and quantum physics," George Mason University computer science professor Richard Gomez told NewsFactor. "It is widely accepted now that, without a doubt, information is physical and quantum physics provides the rules of that physical behavior."
Kieu's work may kill two mathematical birds with one stone by solving the tenth of David Hilbert's famous 23 mathematical problems, which happens to be equivalent to solving Turing's famous "halting problem."
In the year 1900, Hilbert asked for a way to decide whether any algebraic equation involving only whole numbers could be solved using an algorithm or program -- a set of well-defined rules executed in a finite number of steps. This was Hilbert's famous "tenth problem" (of 23). In 1970, this problem was shown to be equivalent to deciding whether an arbitrary computer program would solve the same algebraic equation and "halt," or stop -- Turing's famous "halting problem."
Infinite Search in Finite Time
Kieu believes he has solved both problems. With quantum mechanics, he says he can use a "quantum algorithm" to search through an infinite number of potential solutions to Hilbert's proposed equation and perform the search in a finite period of time. In other words, he can look at every possible solution and be done before dinner!
If there is a solution, he will see it -- and since he has seen every possible solution, he will know whether the equation can be solved using his algorithm (Hilbert's problem), and he will know whether his "quantum computer" will halt, since it is done computing (Turing's problem).
"Our quantum algorithm could, in fact, be regarded as an infinite search through the integers in a finite amount of time -- the type of search required to solve the Turing halting problem," Kieu explained.
"The weirdness of quantum mechanics allows us to work with all information in new ways," Dr. Gomez told NewsFactor. "Tien Kieu simply takes advantage of the rules of quantum physics to achieve results that, in the classical world, he could not."
Just where to put a quantum computer that can search through an infinite number of potential solutions to a given problem may be tantamount to asking where a 900-pound gorilla should sleep. "Anywhere and everywhere" may be the smartest answer to both questions.
"We are still trying to figure out where all the quantum calculations are going to take place, since there are not enough atoms in the universe -- about 10 to the power of 80 -- to do the calculations and store the qubits -- individual bits of quantum information," Dr. Gomez explained. "David Deutsch says the calculations will occur in an infinite number of other universes that exist parallel to ours. Go figure."
So if I say that a joke is funny, they can provide the quantum rules describing why?
And also why you may not think it's funny?
This theory may well be neato spiffy, but it's not universal.
He was a pretty moody, emotional individual with many personal issues and he left no suicide note of any kind.
His conviction occurred in March 1952. He died in June 1954. I doubt that it took him more than two years to realize that he received a slap on the wrist on a public indecency charge, and that only then did he decide to commit suicide with a two-year-old incident as his motive.
One question which Wittgenstein concerned himself with is the rules of language. He postulated a language which consisted of two speakers, one of whom was a mason and the other of whom was a mason's assistant. The language had two words - "brick" and "mortar". Each time the mason uttered "brick" it meant that the assistant would hand him a brick and each time he said "mortar" the assistant would provide him with mortar. Wittgenstein postulated that even in so impoverished a system humor would be possible - the one type of joke in this language would be if the mason said "mortar" and the assistant handed him a "brick" instead.
I have doubts about this. The same with Von Neuman who is also given the same credit. I don't know why we seize on such figures and give them exaggerated importance.
But it's only funny if the mason thinks its funny, and perhaps also only if the assistant meant it to be funny. Otherwise, it's a mistake. Or it was a protest on the part of the assistant. Or several other alternate possibilities I can think of.
And again, what's "funny" between these two masons may not be "funny" between the next pair. So "humor" has some characteristics that are independent of this primitive two-word language.
The point being that "humor" in that simple system presumes the existence of non-concrete information over and above the simple passing of brick and mortar, so that they can tell the difference between humor and something else. It requires the existence of meaning beyond brick-and-mortar interaction.
It's interesting how many thinkers have grappled with this issue in one form or other:
Turing and the halting problem in computer science
Carl Schmitt and the Ausnahmezustand in political science and legal theory
Wittgenstein and language games in language theory
Godel and the undecidability problem in mathematics
Heisenberg and the uncertainty principle in physics
Derrida and differance in philosophy
Blanchot and the "death of the writer" in literary theory
Popper and falsifiabilty in the theory of science
MacIntyre and narrative tradition in ethics and moral philosophy
And the list goes on.