7 ms·

Overview pasted here: ———— The thesis asserts this: If an algorithm A computes a partial function f from natural numbers to natural numbers then f is partiall

Overview pasted here: ———— The thesis asserts this: If an algorithm A computes a partial function f from natural numbers to natural numbers then f is partially recursive, i.e., the graph of f is recursively enumerable. The thesis has been formulated in 1930s. The only algorithms at the time were sequential algorithms. Sequential algorithms were axiomatized in 2000. This axiomatization was used in 2008 to prove the thesis for sequential algorithms, i.e., for the case where A ranges over sequential algorithms. These days, in addition to sequential algorithms, there are parallel algorithms, distributed algorithms, probabilistic algorithms, quantum algorithms, learning algorithms, etc. The question whether the thesis is true in full generality is actively discussed from 1960s. We argue that, in full generality, the thesis cannot possibly be true.

berti 8y ago
> We argue that, in full generality, the thesis cannot possibly be true. If you could post a text summary of this part, we'd be very grateful.
- TimTheTinker 8y ago
  I don't have the time to put that together, but here's a somewhat cleaned up (i.e. times and some newlines removed) paste of the closed captions. This may be helpful if you're good at scanning a lot of text. https://gist.github.com/RoyTinker/1a7e27cb4dbd468b45586a380fdb109c https://gist.github.com/RoyTinker/1a7e27cb4dbd468b45586a380f...
olliej 8y ago
I’m still unclear on whether probabilistic algorithms are “algorithms” in the strict sense - in that definition an algorithm should have deterministic behavior, which a probabilistic method does not have. But let’s say your “random” is a deterministic prng- does that then make the PA a deterministic algorithm? Basically the distinction can be best illustrated with bozo/bogo sort. The definition many people use is: 1. Randomly shuffle the input 2. See if it is sorted, if not go to 1. The problem, as explained to me by an algorithms lecturer a long time ago, is that the algorithm is not guaranteed to finish, and more over the same input may or may not result in it finishing on different runs. Per that lecturer a “correct” bozo sort is 1. Generate a list of every permutation of the input 2. Iterate the list until you find a sorted entry and return that. It has computable best case, worst case, and average case (all terrible). It is guaranteed that the same input will always produce the same output (terminate vs not terminate). Obviously you could optimize this if you had an algorithm that could shuffle an input such that you were guaranteed that if you shuffled it’s own output you were guaranteed to produce every ordering of the original input. Then you would get closer to: shuffle; check; repeat. But still note that there is no random involved :)
- hyperion2010 8y ago
  I think that the intuition here has to do with the dimensionality of the problem, in the sense that we have proved that in 3 dimensions a random walk will never return to it's starting point, bit in two dimensions it will. Mapping all probabilistic algorithms into demensional random walk space is probably extremely difficult though.
  - dcow 8y ago
    > in the sense that we have proved that in 3 dimensions a random walk will never return to it’s (sic.) starting point We have? I believe the probability is ~34%. http://mathworld.wolfram.com/PolyasRandomWalkConstants.html http://mathworld.wolfram.com/PolyasRandomWalkConstants.html
    - hyperion2010 8y ago
      Sorry, I had it reversed in my head. For 1 and 2 dimensions they will return to the starting point with probability 1. For 3 dimensions it simply that it is not probability 1. Obviously a weaker result.
- rcfox 8y ago
  Do you have a better source than "an anonymous lecturer once said..."? I've never heard such a strict definition of algorithm before. Randomized algorithms are often used to avoid falling into worst-case scenarios and improve run-time, like with quicksort, or to avoid settling in local minima like with simulated annealing.
  - olliej 8y ago
    Ok per wikipedia (https://en.wikipedia.org/wiki/Algorithm https://en.wikipedia.org/wiki/Algorithm) "Starting from an initial state and initial input (perhaps empty),[4] the instructions describe a computation that, when executed, proceeds through a finite[5] number of well-defined successive states, eventually producing "output"[6] and terminating at a final ending state" The "finite" bit I guess is the key thing, that I think was what my lecturer would have been getting at - the canonical bozo sort is not - you could just run for ever, as you might not /ever/ produce a correctly sorted version of the input. That article also points to "randomized algorithms", taking some random input (you could image random input being an RNG seed I guess?). That article does include monte carlo algorithms, which technically could not terminate (Montecarlo simulation of a bouncing photon could technically go for ever) so I am left confused. The lecturer was Prof. Tadao Takaoka, who was great, and apparently (per google) was on the editorial board of the journal Algorithms (http://www.mdpi.org/algorithms/editors.htm http://www.mdpi.org/algorithms/editors.htm)
hyperion2010 8y ago
Without having looked at the details, why do I feel like all of the other types of algorithms should be able to be shown to be equivalent to the sequential case under the assumption of local realism? That is to say, if you don't consider that an algorithm must be implemented in this universe then I suspect that many things are possible. Am I missing something here?
- sometime 8y ago
  Conversely, those algorithms which cannot be converted to sequential possibly only run on exotic Turing Machines like ones with infinite bands or infinite parallelism and those likely don't have a physical equivalent because it looks like our universe only supports finite computation. In other words, the algorithms which violate Church-Turing might not be interesting at all, or only for analysis in an idealized setting.
  - hyperion2010 8y ago
    Indeed. I had a similar thought, which initially seemed profound. "Maybe this means that the universe can encode the results of non sequential algorithms but no one can ever decode them. Douglas Adams was right all along!" Of course if you can't decode anything then in theory the universe is currently running an infinite number of undecodable simulations of itself right now. Related piece from Scott Aaronson [0]. 0. https://www.scottaaronson.com/blog/?p=3327 https://www.scottaaronson.com/blog/?p=3327
daveFNbuck 8y ago
> These days, in addition to sequential algorithms, there are parallel algorithms, distributed algorithms, probabilistic algorithms, quantum algorithms, learning algorithms, etc. These can all be converted into sequential algorithms with some overhead. Is there an actual proof in the video or just an argument that something that can't be made sequential must exist?
- macleginn 8y ago
  As was proved recently, there are quantum algorithms that can not: https://www.quantamagazine.org/finally-a-problem-that-only-quantum-computers-will-ever-be-able-to-solve-20180621/ https://www.quantamagazine.org/finally-a-problem-that-only-q...
  - atq2119 8y ago
    First of all, the paper that this article is reporting on doesn't actually prove a separation between quantum and classical algorithms at all. It's an oracle separation result, which makes it an important result in complexity theory, but not a statement about actual classical or quantum algorithms. Second, the result is unrelated to the Church-Turing thesis in the first place, since it's only about relative efficiency, whereas the Church-Turing thesis is about computability. Every quantum algorithm can be simulated by a classical computer, so quantum computing cannot possibly disprove the Church-Turing thesis. However, there's a stronger variant of the Church-Turing thesis which also takes performance into account, and it's plausible that quantum computers can contradict this stronger version (although we're very far away from actually proving that).
- jonathanstrange 8y ago
  A parallel OR will terminate even if one of the subclauses does not terminate, whereas sequential OR might not terminate in this case. So if you define an algorithm as a computation that terminates, parallel OR cannot be fully emulated by sequential OR. The problem is that, as far as I know, sequential algorithms form a uniform class, because e.g. equivalence between different sequential models like Turing machines and the untyped lambda calculus can be proved. AFAIK, this is not possible for parallel models of computation, there are different models of them with different expressivity. (I'm not an expert on that, so take this with a grain of salt and please correct me if I'm wrong!)

berti 8y ago

> We argue that, in full generality, the thesis cannot possibly be true. If you could post a text summary of this part, we'd be very grateful.

TimTheTinker 8y ago
I don't have the time to put that together, but here's a somewhat cleaned up (i.e. times and some newlines removed) paste of the closed captions. This may be helpful if you're good at scanning a lot of text. https://gist.github.com/RoyTinker/1a7e27cb4dbd468b45586a380fdb109c https://gist.github.com/RoyTinker/1a7e27cb4dbd468b45586a380f...

olliej 8y ago

I’m still unclear on whether probabilistic algorithms are “algorithms” in the strict sense - in that definition an algorithm should have deterministic behavior, which a probabilistic method does not have. But let’s say your “random” is a deterministic prng- does that then make the PA a deterministic algorithm? Basically the distinction can be best illustrated with bozo/bogo sort. The definition many people use is: 1. Randomly shuffle the input 2. See if it is sorted, if not go to 1. The problem, as explained to me by an algorithms lecturer a long time ago, is that the algorithm is not guaranteed to finish, and more over the same input may or may not result in it finishing on different runs. Per that lecturer a “correct” bozo sort is 1. Generate a list of every permutation of the input 2. Iterate the list until you find a sorted entry and return that. It has computable best case, worst case, and average case (all terrible). It is guaranteed that the same input will always produce the same output (terminate vs not terminate). Obviously you could optimize this if you had an algorithm that could shuffle an input such that you were guaranteed that if you shuffled it’s own output you were guaranteed to produce every ordering of the original input. Then you would get closer to: shuffle; check; repeat. But still note that there is no random involved :)

hyperion2010 8y ago
I think that the intuition here has to do with the dimensionality of the problem, in the sense that we have proved that in 3 dimensions a random walk will never return to it's starting point, bit in two dimensions it will. Mapping all probabilistic algorithms into demensional random walk space is probably extremely difficult though.
- dcow 8y ago
  > in the sense that we have proved that in 3 dimensions a random walk will never return to it’s (sic.) starting point We have? I believe the probability is ~34%. http://mathworld.wolfram.com/PolyasRandomWalkConstants.html http://mathworld.wolfram.com/PolyasRandomWalkConstants.html
  - hyperion2010 8y ago
    Sorry, I had it reversed in my head. For 1 and 2 dimensions they will return to the starting point with probability 1. For 3 dimensions it simply that it is not probability 1. Obviously a weaker result.
rcfox 8y ago
Do you have a better source than "an anonymous lecturer once said..."? I've never heard such a strict definition of algorithm before. Randomized algorithms are often used to avoid falling into worst-case scenarios and improve run-time, like with quicksort, or to avoid settling in local minima like with simulated annealing.
- olliej 8y ago
  Ok per wikipedia (https://en.wikipedia.org/wiki/Algorithm https://en.wikipedia.org/wiki/Algorithm) "Starting from an initial state and initial input (perhaps empty),[4] the instructions describe a computation that, when executed, proceeds through a finite[5] number of well-defined successive states, eventually producing "output"[6] and terminating at a final ending state" The "finite" bit I guess is the key thing, that I think was what my lecturer would have been getting at - the canonical bozo sort is not - you could just run for ever, as you might not /ever/ produce a correctly sorted version of the input. That article also points to "randomized algorithms", taking some random input (you could image random input being an RNG seed I guess?). That article does include monte carlo algorithms, which technically could not terminate (Montecarlo simulation of a bouncing photon could technically go for ever) so I am left confused. The lecturer was Prof. Tadao Takaoka, who was great, and apparently (per google) was on the editorial board of the journal Algorithms (http://www.mdpi.org/algorithms/editors.htm http://www.mdpi.org/algorithms/editors.htm)

hyperion2010 8y ago

Without having looked at the details, why do I feel like all of the other types of algorithms should be able to be shown to be equivalent to the sequential case under the assumption of local realism? That is to say, if you don't consider that an algorithm must be implemented in this universe then I suspect that many things are possible. Am I missing something here?

sometime 8y ago
Conversely, those algorithms which cannot be converted to sequential possibly only run on exotic Turing Machines like ones with infinite bands or infinite parallelism and those likely don't have a physical equivalent because it looks like our universe only supports finite computation. In other words, the algorithms which violate Church-Turing might not be interesting at all, or only for analysis in an idealized setting.
- hyperion2010 8y ago
  Indeed. I had a similar thought, which initially seemed profound. "Maybe this means that the universe can encode the results of non sequential algorithms but no one can ever decode them. Douglas Adams was right all along!" Of course if you can't decode anything then in theory the universe is currently running an infinite number of undecodable simulations of itself right now. Related piece from Scott Aaronson [0]. 0. https://www.scottaaronson.com/blog/?p=3327 https://www.scottaaronson.com/blog/?p=3327

daveFNbuck 8y ago

> These days, in addition to sequential algorithms, there are parallel algorithms, distributed algorithms, probabilistic algorithms, quantum algorithms, learning algorithms, etc. These can all be converted into sequential algorithms with some overhead. Is there an actual proof in the video or just an argument that something that can't be made sequential must exist?

macleginn 8y ago
As was proved recently, there are quantum algorithms that can not: https://www.quantamagazine.org/finally-a-problem-that-only-quantum-computers-will-ever-be-able-to-solve-20180621/ https://www.quantamagazine.org/finally-a-problem-that-only-q...
- atq2119 8y ago
  First of all, the paper that this article is reporting on doesn't actually prove a separation between quantum and classical algorithms at all. It's an oracle separation result, which makes it an important result in complexity theory, but not a statement about actual classical or quantum algorithms. Second, the result is unrelated to the Church-Turing thesis in the first place, since it's only about relative efficiency, whereas the Church-Turing thesis is about computability. Every quantum algorithm can be simulated by a classical computer, so quantum computing cannot possibly disprove the Church-Turing thesis. However, there's a stronger variant of the Church-Turing thesis which also takes performance into account, and it's plausible that quantum computers can contradict this stronger version (although we're very far away from actually proving that).
jonathanstrange 8y ago
A parallel OR will terminate even if one of the subclauses does not terminate, whereas sequential OR might not terminate in this case. So if you define an algorithm as a computation that terminates, parallel OR cannot be fully emulated by sequential OR. The problem is that, as far as I know, sequential algorithms form a uniform class, because e.g. equivalence between different sequential models like Turing machines and the untyped lambda calculus can be proved. AFAIK, this is not possible for parallel models of computation, there are different models of them with different expressivity. (I'm not an expert on that, so take this with a grain of salt and please correct me if I'm wrong!)