3 ms·

> Also take a look at the Church-Turing thesis The Church-Turing thesis is an (unprovable) statement of faith, not a mathematical theorem. Effectively, it sta

> Also take a look at the Church-Turing thesis The Church-Turing thesis is an (unprovable) statement of faith, not a mathematical theorem. Effectively, it states that "all algorithms can be computed on a Turing machine, and vice-versa". Note that this thesis is not as radical as it first sounds; I'm assuming that if we ever do find a way of computing functions that cannot be computed on a Turing machine, then we'll just call it something else, not an 'algorithm'. This would make the Church-Turing thesis just a tautological circular definition.

javra 11y ago
Well, normally one makes the thesis concrete by saying that lambda calculus and Turing machines yield an equivalent notion of computability.
jimhefferon 11y ago
> it states that "all algorithms can be computed on a Turing machine, and vice-versa". It is about algorithms of a certain kind, the kind of computation that we do when we, say, factor polynomials or check a step in a euclidean geometry proof. That is the kind of computation called for in the Entscheidungsproblem. Turing's analysis of that kind of computation was very persuasive, and consequently influential. But as to whether there is more, whether we can go farther with some kind of analog computation involving lasers and interference, or some kind of quantum stuff ... well, maybe. It doesn't seem impossible that Turing, in the 1930's, lying on the grassy river bank after a hard run and reflecting on what a device can compute, did not imagine it all. To date (as I understand it) no analysis of what can be done with a real device under current physics has for the community of experts the same persuasiveness of Turing's work. This paper seems to me to at least hint that there may be things that nature computes, but which no Turing machine can compute. It makes me wish to understand the physics.

javra 11y ago

Well, normally one makes the thesis concrete by saying that lambda calculus and Turing machines yield an equivalent notion of computability.

jimhefferon 11y ago

> it states that "all algorithms can be computed on a Turing machine, and vice-versa". It is about algorithms of a certain kind, the kind of computation that we do when we, say, factor polynomials or check a step in a euclidean geometry proof. That is the kind of computation called for in the Entscheidungsproblem. Turing's analysis of that kind of computation was very persuasive, and consequently influential. But as to whether there is more, whether we can go farther with some kind of analog computation involving lasers and interference, or some kind of quantum stuff ... well, maybe. It doesn't seem impossible that Turing, in the 1930's, lying on the grassy river bank after a hard run and reflecting on what a device can compute, did not imagine it all. To date (as I understand it) no analysis of what can be done with a real device under current physics has for the community of experts the same persuasiveness of Turing's work. This paper seems to me to at least hint that there may be things that nature computes, but which no Turing machine can compute. It makes me wish to understand the physics.