Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Church-Turing-Deutsch principle and Incompleteness-Halting.

  1. Nov 28, 2016 #1

    n01

    User Avatar

    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.
     
  2. jcsd
  3. Nov 30, 2016 #2
    Something like the CTD is impossible to prove. At best it's a motivating chant for physicists. :p
     
  4. Nov 30, 2016 #3

    n01

    User Avatar

    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...
     
  5. Dec 13, 2016 #4
    It seems apparent from Hume's argument on induction.
     
  6. Dec 22, 2016 #5

    StatGuy2000

    User Avatar
    Education Advisor

    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.
     
  7. Dec 22, 2016 #6

    n01

    User Avatar

    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/
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Church-Turing-Deutsch principle and Incompleteness-Halting.
  1. Incompleteness Theroem (Replies: 18)

Loading...