Turing machine, computable function.

In summary: . in summary, some quantum processes appear to generate random numbers that look like they obey some sort of probabilistic turing machine rule, though this has not yet been fully confirmed.
  • #1
bifolco84
7
0
From Nielsen-Chuang:how might we recognize that a process in nature computes a function not computable by a turing machine?
 
Technology news on Phys.org
  • #2
Great question. I am registering to this post in the hope for some answers.
 
  • #3
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.)
 
  • #4
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...
 
  • #5
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.
 
  • #6
Coin said:
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
 
  • #7
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.
 
  • #8
Nice link...thanks
 

1. What is a Turing machine?

A Turing machine is a theoretical mathematical model of a computing device that can manipulate symbols on a tape according to a set of rules. It was first proposed by Alan Turing in 1936 and is considered to be the foundation of modern computing.

2. How does a Turing machine work?

A Turing machine consists of a tape divided into cells, a read/write head that can read and write symbols on the tape, and a set of rules that dictate the machine's behavior. The machine starts at a specific cell on the tape and follows the rules to move the head, read and write symbols, and change its internal state. This process continues until the machine reaches an accepting or rejecting state.

3. What is a computable function?

A computable function, also known as a recursive function, is a mathematical function that can be calculated by a Turing machine. It is a function that takes an input and produces an output, and the steps to calculate the output can be broken down into finite, simple steps that a Turing machine can perform.

4. Can all functions be computed by a Turing machine?

Yes, it is believed that all functions that can be computed by any method can also be computed by a Turing machine. This is known as the Church-Turing thesis and is a fundamental concept in theoretical computer science.

5. How is a Turing machine different from a modern computer?

A Turing machine is a theoretical model and does not represent any physical computing device. It has a limited memory and can only perform simple operations, whereas a modern computer has significantly more memory and can perform complex operations. However, all modern computers are based on the principles of a Turing machine, making it a crucial concept in computer science.

Similar threads

  • Programming and Computer Science
Replies
29
Views
2K
  • Programming and Computer Science
Replies
1
Views
748
  • Programming and Computer Science
Replies
25
Views
3K
  • Programming and Computer Science
Replies
1
Views
864
  • Programming and Computer Science
Replies
2
Views
1K
  • Programming and Computer Science
Replies
2
Views
717
  • Programming and Computer Science
Replies
3
Views
1K
  • Programming and Computer Science
Replies
2
Views
1K
  • Programming and Computer Science
Replies
25
Views
2K
  • Programming and Computer Science
Replies
6
Views
2K
Back
Top