5 ms·

> The speaker would simply have to point to a concrete algorithm that can be performed by a person with pencil and paper but not by a Turing machine (or vice ve

> The speaker would simply have to point to a concrete algorithm that can be performed by a person with pencil and paper but not by a Turing machine (or vice versa). No, this is a circular definition. We define an "algorithm" as something that can be performed by a Turing machine. So the Church-Turing thesis is a trivial tautology. (Though of course a useless one.)

thfuran 8y ago
That's a peculiar definition of algorithm.
roywiggins 8y ago
Not quite: https://en.wikipedia.org/wiki/Effective_method https://en.wikipedia.org/wiki/Effective_method "- It consists of a finite number of exact, finite instructions. - When it is applied to a problem from its class: - It always finishes (terminates) after a finite number of steps. - It always produces a correct answer. - In principle, it can be done by a human without any aids except writing materials. - Its instructions need only to be followed rigorously to succeed. In other words, it requires no ingenuity to succeed." "Several independent efforts to give a formal characterization of effective calculability led to a variety of proposed definitions (general recursion, Turing machines, λ-calculus) that later were shown to be equivalent."
justinpombrio 8y ago
> No, this is a circular definition. We define an "algorithm" as something that can be performed by a Turing machine. So the Church-Turing thesis is a trivial tautology. (Though of course a useless one.) No, that's a terrible definition, and it isn't what computer scientists typically use, though it might be what one says if they're not careful. If someone says that "algorithm" means "what a Turing machine can compute", it's because they believe the Church-Turing thesis, which says that they're the same. If they're the same, then you can talk about them interchangeably, and "Turing machine computations" have a cleaner definition than "pen and paper algorithms", so it's convenient to talk about "Turing machine computations" as if that's the ground truth. But if the Church-Turing thesis is false, then they're not the same, and you should be very careful not to mix them up. And we need a word for "the sorts of things you can compute by hand by a set of well-defined steps", and that's what "algorithm" has always meant. EDIT: Note that I'm making a prediction. If a person told you that "algorithm" means "what a Turing machine can compute", ask them what "algorithm" means if the Church-Turing thesis is false. My prediction is that they'll use a different defintion, based on what you can effectively compute by hand, like the "Effective Method" wikipedia article that my sibling posted.
SilasX 8y ago
Yeah, I would refine that definition to "point a concrete problem that can provably be solved by [some] humans, and provably not by a TM". Concretely, that problem might look something like: "Given N non-communicating humans, each of whom see the same 1000x1000 b/w grid. Emit the same answer as 99% of the humans to the question of whether the grid contains a Q." That would be a problem where, if you could prove that humans can do it, but TMs can't, you've refuted the CTT. Do I have that right?

thfuran 8y ago

That's a peculiar definition of algorithm.

roywiggins 8y ago

Not quite: https://en.wikipedia.org/wiki/Effective_method https://en.wikipedia.org/wiki/Effective_method "- It consists of a finite number of exact, finite instructions. - When it is applied to a problem from its class: - It always finishes (terminates) after a finite number of steps. - It always produces a correct answer. - In principle, it can be done by a human without any aids except writing materials. - Its instructions need only to be followed rigorously to succeed. In other words, it requires no ingenuity to succeed." "Several independent efforts to give a formal characterization of effective calculability led to a variety of proposed definitions (general recursion, Turing machines, λ-calculus) that later were shown to be equivalent."

justinpombrio 8y ago

> No, this is a circular definition. We define an "algorithm" as something that can be performed by a Turing machine. So the Church-Turing thesis is a trivial tautology. (Though of course a useless one.) No, that's a terrible definition, and it isn't what computer scientists typically use, though it might be what one says if they're not careful. If someone says that "algorithm" means "what a Turing machine can compute", it's because they believe the Church-Turing thesis, which says that they're the same. If they're the same, then you can talk about them interchangeably, and "Turing machine computations" have a cleaner definition than "pen and paper algorithms", so it's convenient to talk about "Turing machine computations" as if that's the ground truth. But if the Church-Turing thesis is false, then they're not the same, and you should be very careful not to mix them up. And we need a word for "the sorts of things you can compute by hand by a set of well-defined steps", and that's what "algorithm" has always meant. EDIT: Note that I'm making a prediction. If a person told you that "algorithm" means "what a Turing machine can compute", ask them what "algorithm" means if the Church-Turing thesis is false. My prediction is that they'll use a different defintion, based on what you can effectively compute by hand, like the "Effective Method" wikipedia article that my sibling posted.

SilasX 8y ago

Yeah, I would refine that definition to "point a concrete problem that can provably be solved by [some] humans, and provably not by a TM". Concretely, that problem might look something like: "Given N non-communicating humans, each of whom see the same 1000x1000 b/w grid. Emit the same answer as 99% of the humans to the question of whether the grid contains a Q." That would be a problem where, if you could prove that humans can do it, but TMs can't, you've refuted the CTT. Do I have that right?