- #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?
Coin said:Bohmian Mechanics
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.
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.
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.
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.
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.