Strictly speaking that is the “correct” implementation of bogosort because it is deterministic (per my algorithms lecturer: for it to be an algorithm you must take the same steps each time for a given input. Obviously you could get around this by having the sort function take a seed and implement an RNG)

There are various definitions of "algorithm", but that one seems needlessly restrictive. Randomized algorithms are a thing, and there doesn't seem to be much reason to exclude them, to me.

I think the specific issue with the "randomly sort and see if its sorted" is that it is not guaranteed to ever complete.

Can't the same be said about the algorithm to generate the Collatz sequence for any given number? By that definition, I shouldn't be calling that an algorithm.

Is collatz the 2n+1&n/3 one?

Any way the algorithm to get the next number in a collatz sequence is deterministic and has best and worst case complexity of O(1).

You’re then just choosing to run that algorithm against its own output a (potentially) infinite amount of times.

That said I take you point. I realize in another reply that what I had totally failed to recognize was my lecturer not clearly explaining that the definition he used was that an algorithm must be executable on a Turing machine.

Yeah, Collatz operation is: if it's even divide by 2, otherwise multiply by 3 and add 1.

The gp post is asking: what if you make a procedure that runs that on a given input number, repeatedly, until you end up with the output 1, and give the sequence of numbers you visited on the way. Is that an algorithm?

Every number we've tried so far does go to 1, but it's unproven if they all do. It's possible that there exist cycles not containing 1, or maybe some inputs go to infinity. We haven't been able to prove either way.

> [...] the definition he used was that an algorithm must be executable on a Turing machine

Yeah, that's a pretty good reason to choose a certain definition of an algorithm (that otherwise might be awkward) when you have a model you're fitting it into.

It is an overly strict interpretation of that rule to assume it prohibits any randomized algorithm.

Aren't these the same steps for any given input?

  1) Roll dice to get random number N
  2) Get the Nth permutation of the input sequence (for some ordering of permutations)
  3) Permute input sequence
  4) If sorted: done, else goto step 1

You have to specify the output of rolling the die. If you use an RNG you would provide the seed state for the RNG as an input to the algorithm.

Think of it as “can I run this algorithm on a Turing machine”

it's even better, isn't it? next_permutation returns false once it rolls over and returns the sorted version so you can drop the negation.