Turing machine, computable function.

[bifolco84]

From Nielsen-Chuang:how might we recognize that a process in nature computes a function not computable by a turing machine?

 

[omaradib]

Great question. I am registering to this post in the hope for some answers.

 

[Coin]

CHEAP ANSWER: If it outputs a true random number, such as some quantum processes appear to. A turing machine cannot do this, you need a probabilistic turing machine for this. (A probabilistic turing machine is not considered more powerful than a normal turing machine with regard to computability by computer scientists because it accepts the same languages, but you asked about "computing a function", which is maybe a slightly different question...)

REAL ANSWER: You cannot, because our ability to observe the universe is limited and you cannot fully observe what any system in nature is doing. If there is a process that appears to be computable, we cannot rule out the possibility that on scales finer than we can currently observe there are fluctuations that are based on something uncomputable. If there is a process that appears to be uncomputable, it might actually turn out that if we had a more complete description of the laws of nature it would turn out to be doing something simpler and computable behind the scenes. (Even the random numbers apparently generated by quantum processes might be based on a deterministic process we cannot see the machinery for.)

 

[schip666!]

Pertaining to <REAL ANSWER...>

Are you referencing some kind of quantum "hidden variable" theory? And if so (or even not) can you provide a clear -- if there can be -- description of the ins'n'outs of the current thinking on such theories? The wiki page is kinda thin...

 

[Coin]

Well, my point was only that we can't discount the possibility.

But that said if you're interested in modern hidden variable theories the magic word to google for is "Bohmian". Bohmian Mechanics is a nonlocal hidden variables theory that as I understand all modern work on hidden variables has aggregated around, and it incidentally does have the property that the "random" values in quantum theory arise from the statistics of deterministic processes. As I understand Bohmian theory is a serious idea, but is not considered especially important by mainstream scientists because it does not have practical application (ie, since the entire point is that Bohmian mechanics replicates copenhagen-interpretation QM exactly, it is not expected that if Bohmian mechanics were accurate, it would actually tell us anything). Probably the computer science forum is not the best place to ask about this.

 

[schip666!]

Bohmian Mechanics

Yeah I got that idea, I was wondering if there was any real work being done on it or if it was pretty much a dead end at this point. I get the impression that most Quantum Mechanics think that there is no way to "see beyond the veil" and that things are really just random under the covers there.

thanks

 

[Coin]

schip, as I understand there is real work being done on it but only by a very small group of people. There was some sort of conference held on the subject just last month (you may find the slides from the two "introductory talks" at the top of particular interest). Whether it is a "dead end" would be a matter of opinion, though I think the group of people whose opinion is that it is something other than a dead end are by far in the minority. Again I think you probably would be able to get more useful information if you ask in some other section of this forum, possibly the "Beyond the Standard Model" section.

 

[schip666!]

Nice link...thanks