Free Republic
Browse · Search
News/Activism
Topics · Post Article

Skip to comments.

Quantum Leaps May Solve Impossible Problems
NewsFactor Network ^ | October 7, 2002 | Mike Martin

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."


TOPICS: Technical
KEYWORDS: alanturing; alonzochurch; davidhilbert; quantumphysics; realscience; richardgomez; stringtheory; techindex; tienkieu; turingchurchthesis
Navigation: use the links below to view more comments.
first 1-2021-4041-44 next last

1 posted on 10/10/2002 11:58:04 AM PDT by sourcery
[ Post Reply | Private Reply | View Replies]

To: A tall man in a cowboy hat; Libertarianize the GOP; Free the USA; Ernest_at_the_Beach
FYI
2 posted on 10/10/2002 11:59:36 AM PDT by sourcery
[ Post Reply | Private Reply | To 1 | View Replies]

To: *tech_index; *RealScience; Physicist
http://www.freerepublic.com/perl/bump-list
3 posted on 10/10/2002 12:02:55 PM PDT by Free the USA
[ Post Reply | Private Reply | To 1 | View Replies]

To: sourcery
"It is widely accepted now that, without a doubt, information is physical and quantum physics provides the rules of that physical behavior."

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.

4 posted on 10/10/2002 12:03:37 PM PDT by r9etb
[ Post Reply | Private Reply | To 1 | View Replies]

To: sourcery
I couldn't find a link to his publication. I'll have to read to see if he's correct.
5 posted on 10/10/2002 12:06:31 PM PDT by Doctor Stochastic
[ Post Reply | Private Reply | To 1 | View Replies]

To: sourcery
The universe is exactly what we "THINK" it is.
6 posted on 10/10/2002 12:08:39 PM PDT by Consort
[ Post Reply | Private Reply | To 1 | View Replies]

To: sourcery
Just a note on the editorial slant of this article: Turing's legal problems associated with cruising young men in public places has never been established as his motivation for suicide.

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.

7 posted on 10/10/2002 12:09:20 PM PDT by wideawake
[ Post Reply | Private Reply | To 1 | View Replies]

To: wideawake
I suppose if Tien Kieu's work is correct, I'll just say thank you.
8 posted on 10/10/2002 12:13:30 PM PDT by Doctor Stochastic
[ Post Reply | Private Reply | To 7 | View Replies]

DONATE TODAY!!!.
SUPPORT FREE REPUBLIC

Donate Here By Secure Server

Or mail checks to
FreeRepublic , LLC
PO BOX 9771
FRESNO, CA 93794

or you can use

PayPal at Jimrob@psnw.com
STOP BY AND BUMP THE FUNDRAISER THREAD


9 posted on 10/10/2002 12:13:33 PM PDT by Anti-Bubba182
[ Post Reply | Private Reply | To 7 | View Replies]

To: wideawake
OTOH, Turing is something of a gay icon. I once began reading a short biography of him. I had to stop once the author began referring to him only (and often) as "Alan," and began waxing poetic about him in a most unscientific manner. It began reading like something written by a 6th grade girl in the throes of her first crush. Yuck.
10 posted on 10/10/2002 12:15:03 PM PDT by r9etb
[ Post Reply | Private Reply | To 7 | View Replies]

To: r9etb
A lot of this theory has been filtered through the insights of Claude Shannon's information theory and Wittgenstein's linguistic theory.

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.

11 posted on 10/10/2002 12:15:23 PM PDT by wideawake
[ Post Reply | Private Reply | To 4 | View Replies]

To: wideawake
It'd be funnier if, when the mason said "mortar," the assistant gave him the equivalent of a mortar pie in the face.
12 posted on 10/10/2002 12:19:03 PM PDT by LibWhacker
[ Post Reply | Private Reply | To 11 | View Replies]

To: sourcery
Alonzo Church and Alan Turing, who essentially invented the modern-day computer.

------------------------

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.

13 posted on 10/10/2002 12:23:09 PM PDT by RLK
[ Post Reply | Private Reply | To 1 | View Replies]

To: wideawake
And, it would be a different type of joke than the one postulated by Wittgenstein.
14 posted on 10/10/2002 12:24:16 PM PDT by LibWhacker
[ Post Reply | Private Reply | To 11 | View Replies]

To: wideawake
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.

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.

15 posted on 10/10/2002 12:25:06 PM PDT by r9etb
[ Post Reply | Private Reply | To 11 | View Replies]

To: sourcery
I never understand everything about Quantum Physics, but I also never tire of reading about it. It is such a fascinating field.
16 posted on 10/10/2002 12:31:38 PM PDT by WVNan
[ Post Reply | Private Reply | To 1 | View Replies]

To: sourcery
OOOOOOWWWWWWW... Me head hurt.
17 posted on 10/10/2002 12:36:21 PM PDT by Honcho
[ Post Reply | Private Reply | To 1 | View Replies]

To: r9etb
Exactly. Which leads to the conundrum of language - what W called "language games". Language is a game with certain rules. To interpret statements one looks to the rules, but then to interpret the application of those rules, one needs rules of interpretation, and so on ad infinitum.

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.

18 posted on 10/10/2002 12:36:49 PM PDT by wideawake
[ Post Reply | Private Reply | To 15 | View Replies]

To: sourcery
42

Mark
19 posted on 10/10/2002 12:49:09 PM PDT by MarkL
[ Post Reply | Private Reply | To 1 | View Replies]

To: sourcery
hummmm..........someone please post a picture of Ann Coulter, I've got a headache. ;-)
20 posted on 10/10/2002 12:58:40 PM PDT by cd jones
[ Post Reply | Private Reply | To 1 | View Replies]


Navigation: use the links below to view more comments.
first 1-2021-4041-44 next last

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.

Free Republic
Browse · Search
News/Activism
Topics · Post Article

FreeRepublic, LLC, PO BOX 9771, FRESNO, CA 93794
FreeRepublic.com is powered by software copyright 2000-2008 John Robinson