Church-Turing Thesis Cannot Possibly Be True [video]

Re:Church-Turing Thesis Cannot Possibly Be True [video] by shoo on Friday October 19, 2018 @03:20AM (#18254756)

small thought experiment: what if we decouple the issue of "finite" from the probabilistic aspect?

Perhaps-Algorithm A:

  step 1: x := sample a value from a roll of a fair D6
  step 2: print x

Is Perhaps-Algorithm A an algorithm?

Can we argue that we're in a well defined state after step 1 has executed? We have some variable x bound to one value from {1, ..., 6}, with a known probability distribution, although we don't know which integer we've got.

edit: on the other hand perhaps we're just haggling over definitions here. it is definitely the case that non-terminating algorithms exist and can be useful, and non-deterministic algorithms exist and can be useful. it might be the case that some powerful theory and analysis restricts attention to terminating, deterministic algorithms, it doesnt meant that that's all there is.

[ Parent | on HN ]

Re:Church-Turing Thesis Cannot Possibly Be True [video] by olliej on Friday October 19, 2018 @12:41PM (#18257944)

The problem is that because it’s random there is a chance it will never complete, so the same input alternates between halting and non-halting, so the average time is infinite. Which is clearly nonsensical, hence it isn’t an algorithm.

[ Parent | on HN ]