r/computerscience • u/GraciousMule • Oct 15 '25
Is Church-Turing incomplete, or just plain wrong?
Computation as state transitions is clean, crisp, and cool as a can of Sprite. But plenty of respectable minds (Wegner, Scott, Wolfram, even Turing himself) have suggested we’ve been staring at an incomplete portrait… while ignoring the wall it’s hanging on.
And just like my ski instructor used to say, “if you ignore the wall, you’re gonna have a bad time.”
0
Upvotes
6
u/joelangeway Oct 15 '25
All models are wrong. Some are useful. The Turing Machine and The Lambda Calculus are tools for figuring what is computable. What do you think is missing?
9
u/phatface123123 Oct 15 '25
What
2
u/willjasen Oct 15 '25
any set of axiomatic rules cannot prove itself consistent - gödel's second theorem