3 ms·
I'm no expert myself, but I thought the Turing-Church thesis implied the exact opposite. Turing machines and lambda calculus are widely assumed -- though not pr
by truantbuick 13y ago
I'm no expert myself, but I thought the Turing-Church thesis implied the exact opposite. Turing machines and lambda calculus are widely assumed -- though not proved -- to be the limits of what can be computed. And yet, in a Gödelian fashion, for a given computer (equiv. set of finite axioms), you can always formulate deterministically true statements that cannot be computed.
Note that the formulation of these are counter-examples and thus assert a fundamental limit of computation, but it says nothing that there might be many other things that are non-computable that do not fit the form of these counter-examples.
- eli_gottlieb 13y agoHence why I'd said Turing-recognizable rather than Turing-decidable.