Turing machine and quantum computers

bifolco84
Messages
7
Reaction score
0
Can anyone help me...from Nielsen-Chuang "quantum computation and quantum information":how might we recognize that a process in nature computes a function not computable by a turing machine?
 
Physics news on Phys.org
how might we recognize that a process in nature computes a function not computable by a turing machine
This can not be proven by observations alone. The strong hint would be that the system could not be described by any simple equation.

For any function (computable or not) there exists a Turing machine that can reproduce an arbitrary large finite subset of it. So if you have a black box producing some output, then you never know whether there is an uncomputable system inside or just a very smart Turing machine.
 

Thread 'Quantum Entanglement is a Kinematic Fact, not a Dynamical Effect'

Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. Towards the end of the first lecture for the Qiskit Global Summer School 2025, Foundations of Quantum Mechanics, Olivia Lanes (Global Lead, Content and Education IBM) stated... Source: https://www.physicsforums.com/insights/quantum-entanglement-is-a-kinematic-fact-not-a-dynamical-effect/ by @RUTA
View full post »

Thread 'Quantum behaviour of an electron around a positively charged sphere'

If we release an electron around a positively charged sphere, the initial state of electron is a linear combination of Hydrogen-like states. According to quantum mechanics, evolution of time would not change this initial state because the potential is time independent. However, classically we expect the electron to collide with the sphere. So, it seems that the quantum and classics predict different behaviours!
View full post »

Similar threads

I Discover Beginner-Friendly Books on Quantum Information and Computation | Q&A
Replies
8
Views
4K
I How to understand quantum computers?
Replies
9
Views
2K
A Can humans really create the quantum computer they expected?
Replies
2
Views
1K
I [Quantum Computing] Quantum Parallelism State Calculation
Replies
1
Views
1K
B Quantum Computers and their special properties?
Replies
4
Views
1K
Is Alan Turing given too much credit when it comes to computers?
Replies
29
Views
5K
Insights Quantum Computing for Beginners
Replies
19
Views
4K
I Proving The Church-Turing-Deutsch Principle
Replies
39
Views
6K
I Could a quantum computer simulate any system based on different types of logic?
Replies
2
Views
1K
B Understanding the Intricacies of Quantum Computers and Their Limitations
Replies
8
Views
2K

Hot Threads

Recent Insights

Back
Top