Note: this topic is from 10/10/2002. Thanks sourcery.
· String Theory Ping List ·
· Join · Bookmark · Topics · Google ·
· View or Post in 'blog · post a topic · subscribe ·
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."
Halting Hilbert
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.
Weird Science
"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."
Astronomers Deal Blow To Quantum Theories Of Time, Space, Gravity
Space Daily | Huntsville - Mar 28, 2003 | Editorial Staff
Posted on 03/28/2003 5:49:29 PM PST by vannrox
http://www.freerepublic.com/focus/f-news/878827/posts
Note: this topic is from 10/10/2002. Thanks sourcery.
Disclaimer: Opinions posted on Free Republic are those of the individual posters and do not necessarily represent the opinion of Free Republic or its management. All materials posted herein are protected by copyright law and the exemption for fair use of copyrighted works.