News for hackers. Stuff that matters.
Re:Church-Turing Thesis Cannot Possibly Be True [video] by otabdeveloper1 on Friday October 19, 2018 @08:34AM (#18256250)
> 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.)

Re:Church-Turing Thesis Cannot Possibly Be True [video] by justinpombrio on Friday October 19, 2018 @11:01AM (#18257151)
> 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.

Re:Church-Turing Thesis Cannot Possibly Be True [video] by roywiggins on Friday October 19, 2018 @10:25AM (#18256916)
Not quite:

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."

Re:Church-Turing Thesis Cannot Possibly Be True [video] by SilasX on Friday October 19, 2018 @01:15PM (#18258216)
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?

Re:Church-Turing Thesis Cannot Possibly Be True [video] by thfuran on Friday October 19, 2018 @09:51AM (#18256701)
That's a peculiar definition of algorithm.