Church-Turing-Deutsch principle and Incompleteness-Halting.

[n01]

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.

 

[DuckAmuck]

Something like the CTD is impossible to prove. At best it's a motivating chant for physicists. :p

 

[n01]

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...

 

[DuckAmuck]

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.

 

[StatGuy2000]

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.

 

[n01]

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/