3 ms·
The Church-Turing thesis is not logically provable, as it asserts that an informal concept, 'any solvable problem', can be formally defined as 'any problem solv
by tsimionescu 6y ago
The Church-Turing thesis is not logically provable, as it asserts that an informal concept, 'any solvable problem', can be formally defined as 'any problem solvable by a Turing machine', or equivalently by a few other models of computation (primitive recursive functions, lambda calculus, others discovered in the meantime).
The equivalency of the formal models is well-proven. However, equivalency between a formal construct and an informal human idea is outside the realm of what we can even attempt to currently prove.