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

first

To: **A tall man in a cowboy hat; Libertarianize the GOP; Free the USA; Ernest_at_the_Beach**

FYI

To: ***tech_index; *RealScience; Physicist**

To: **sourcery**

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.

To: **sourcery**

I couldn't find a link to his publication. I'll have to read to see if he's correct.

To: **sourcery**

The universe is exactly what we "THINK" it is.

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.

To: **wideawake**

I suppose if Tien Kieu's work is correct, I'll just say thank you.

PO BOX 9771

FRESNO, CA 93794

STOP BY AND BUMP THE FUNDRAISER THREAD

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.

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.

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.

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.

To: **wideawake**

And, it would be a different type of joke than the one postulated by Wittgenstein.

To: **wideawake**

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.

To: **sourcery**

I never understand everything about Quantum Physics, but I also never tire of reading about it. It is such a fascinating field.

To: **sourcery**

OOOOOOWWWWWWW... Me head hurt.

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.

To: **sourcery**

42

Mark

Mark

To: **sourcery**

hummmm..........someone please post a picture of Ann Coulter, I've got a headache. ;-)

first

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

FreeRepublic.com is powered by software copyright 2000-2008 John Robinson