26 ms·
> and proving that a very simple physical machine can perform any computation (Turing completeness) Not proving, conjecturing. It's not proven until this day:
by nightcracker 5y ago
> and proving that a very simple physical machine can perform any computation (Turing completeness)
Not proving, conjecturing. It's not proven until this day: https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis
- skissane 5y agoIt can never be “proven” because the notion of “any computation” being referred to is informal. Also, it can’t perform any computation, if we say hypercomputation is a form of computation. Hypercomputation is (as far as we know) physically impossible, but so strictly speaking are Turing machines - a true Turing machine has unlimited storage, and an unlimited amount of time in which to complete its computations - any Turing machine you could physically construct would only be a finite approximation of a real one.
- bjornsing 5y agoAh, ok, I should have said “any computation that can be performed by any Turing Machine”.