Church-Turing-Deutsch principle and Incompleteness-Halting.

  • I
  • Thread starter n01
  • Start date
  • Tags
    Principle
In summary, the Church-Turing-Deutsch Principle states that any physical law can be computed. However, this principle has not been proven to be true, and there are potential implications for the Incompleteness Theorem and the Halting problem.
  • #1
n01
49
4
The Church-Turing-Deutsch Principle states that any physical law can be computed.

This is a strong statement which many physicists assume without justification to be true at face value. However, I have not seen proof of the CTD principle being true.

From what I understand David Deutsch postulated this principle in regards to the feasibility of creating quantum computers and potentially justifying Everettian QM.

My question regarding the CTD principle is that what implications does the Incompleteness Theorem or the Halting problem have in regards to computing every physical law? Does the Incompleteness theorem or Halting problem deny the possibility of there existing a computer sophisticated enough to compute every physical law in existence?

Thank you.
 
Physics news on Phys.org
  • #2
Something like the CTD is impossible to prove. At best it's a motivating chant for physicists. :p
 
  • Like
Likes n01
  • #3
DuckAmuck said:
Something like the CTD is impossible to prove

Is it possible to prove that it is impossible to prove?

Or maybe it's just undecidable or never halting in that it is neither possible nor impossible to prove...
 
  • #4
n01 said:
Is it possible to prove that it is impossible to prove?

Or maybe it's just undecidable or never halting in that it is neither possible nor impossible to prove...

It seems apparent from Hume's argument on induction.
 
  • #6
StatGuy2000 said:
Hi n01. I've found an interesting blog entry which asks some of the very questions you are addressing.

http://michaelnielsen.org/blog/interesting-problems-the-church-turing-deutsch-principle/

Please note that the blog entry dates back to 2004, so hopefully someone else will find more up-to-date material that is of relevance to the question posed.

Thank you for the link, StatGuy2000.

I have read that blog post and think the author brings up some valid points about the importance of the Church-Turing-Deutsch Principle.

I have also posted about this same topic in the Quantum Mechanics sub-forum.

Hope anyone else finds this principle as interesting as I do.

https://www.physicsforums.com/threads/proving-the-church-turing-deutsch-principle.894529/
 

Related to Church-Turing-Deutsch principle and Incompleteness-Halting.

What is the Church-Turing-Deutsch principle?

The Church-Turing-Deutsch principle, also known as the Church-Turing thesis, is a hypothesis that states that any algorithmic process can be carried out by a Turing machine. This means that any computation that can be performed by a computer can also be performed by a Turing machine, which is a theoretical model of computation.

What is the importance of the Church-Turing-Deutsch principle?

The Church-Turing-Deutsch principle is important because it serves as the foundation for modern computer science and the theory of computation. It allows us to understand the capabilities and limitations of computers and other computational devices, and provides a framework for analyzing and designing algorithms.

What is the Incompleteness-Halting theorem?

The Incompleteness-Halting theorem, also known as the Incompleteness theorem, is a mathematical proof that demonstrates the limitations of formal axiomatic systems. It was first proposed by mathematician Kurt Gödel in 1931 and states that in any consistent and complete axiomatic system, there will always be statements that cannot be proven or disproven within the system.

What is the connection between the Church-Turing-Deutsch principle and the Incompleteness-Halting theorem?

The Church-Turing-Deutsch principle and the Incompleteness-Halting theorem are both fundamental principles in the field of theoretical computer science. The Church-Turing-Deutsch principle provides a theoretical model for computation, while the Incompleteness-Halting theorem demonstrates the limitations of formal systems and the boundaries of what can be computed.

What are the implications of the Church-Turing-Deutsch principle and the Incompleteness-Halting theorem?

The Church-Turing-Deutsch principle and the Incompleteness-Halting theorem have significant implications for the fields of mathematics, computer science, and philosophy. They shed light on the nature of computation and the limits of human knowledge and reasoning. They also have practical applications in the development of algorithms and computer systems.

Similar threads

  • Quantum Physics
2
Replies
39
Views
6K
  • Set Theory, Logic, Probability, Statistics
Replies
9
Views
1K
  • Computing and Technology
Replies
9
Views
2K
  • Programming and Computer Science
Replies
29
Views
3K
  • Quantum Physics
Replies
4
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
1K
Replies
1
Views
1K
  • Quantum Interpretations and Foundations
Replies
32
Views
2K
  • Quantum Physics
2
Replies
62
Views
7K
  • Science Fiction and Fantasy Media
Replies
13
Views
2K
Back
Top