5 ms·

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

by 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)
- shoo 8y ago
  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.
  - olliej 8y ago
    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.
- rcfox 8y ago
  I think your "correct" bozo sort example from earlier shows that there is a finite number of states (all of the permutations of the input array), just an unbounded number of state transitions. I think for something like this, you could do asymptotic analysis of the expected run-time. Assuming all elements are distinct, there are n! permutations, so each would have a 1/n! chance of being selected each iteration. (But it's rather late, and this is a poor medium for discussing math, and someone has probably already done this, so I'm not going to go any further.)

by rcfox 8y ago

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)

shoo 8y ago
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.
- olliej 8y ago
  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.
rcfox 8y ago
I think your "correct" bozo sort example from earlier shows that there is a finite number of states (all of the permutations of the input array), just an unbounded number of state transitions. I think for something like this, you could do asymptotic analysis of the expected run-time. Assuming all elements are distinct, there are n! permutations, so each would have a 1/n! chance of being selected each iteration. (But it's rather late, and this is a poor medium for discussing math, and someone has probably already done this, so I'm not going to go any further.)