Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Bogo-bogosort

dangermouse.net

Post reply on HN
Print view View original

11–20 of 33 posts

Re: Bogo-bogosort

#11

Post by mikeash »

This got me thinking about a more generalized approach to this sort of thing.

Given a task where you can check completion somehow, you can then solve it using the following procedure:

1. Generate a random program. (This could be a Turing machine, bytecode, C source, whatever.)

2. Execute the program on the input for n steps, where n is an incrementing counter.

3. Execute the given check on the output. If the check passes, return the output.

4. Increment n and go back to 1.

The restriction on n steps avoids running afoul of the Halting Problem.

The check has to be a little more rigorous than the one used in Bogosort. It can't just check to see if the output is in order, because the output may contain completely different numbers, since the program could be doing anything. You'd have to check not only for order but also that the output is in fact a permutation of the input.

I wonder what the running time of this algorithm is. I wonder if it can even be calculated.

Re: Bogo-bogosort

#12

Post by fragsworth »

Here is a "distributed" sorting algorithm that requires even less thinking - you don't even have to write a shuffling algorithm!

1) Start with an empty string.

2) Increment the string in such a way that will eventually generate all strings.

3) Give the string (and your unsorted array) to a processor that attempts to run the string as a program and go back to step 2.

When a processor is given a program, if the output contains all the elements of A and the output is sorted, stop everything! You've sorted the array.

It requires O(n^m) processors, where n is the number of characters possible in a program, and m is the string length of the code that finds the solution. Lots of the processors will be stuck in infinite loops.

Re: Bogo-bogosort

#13

Post by fragsworth »

mikeash wrote: post #11

This got me thinking about a more generalized approach to this sort of thing. Given a task where you can check completion somehow , you can then solve it using the following procedure: 1. Generate a random program. (This could be a Turing machine, bytecode, C source, whatever.) 2. Execute the program on the input for n steps, where n is an incrementing counter. 3. Execute the given check on the output. If the check p…

We both came up with nearly the same idea at nearly the same time (within one minute) - what are the odds of that?

My solution is slightly different - to avoid the Halting Problem, you can use a distributed approach. You have a very large (but finite) number of processors that you pass your programs to.

Re: Bogo-bogosort

#14

Post by mikeash »

fragsworth wrote: post #13
mikeash wrote: post #11

This got me thinking about a more generalized approach to this sort of thing. Given a task where you can check completion somehow , you can then solve it using the following procedure: 1. Generate a random program. (This could be a Turing machine, bytecode, C source, whatever.) 2. Execute the program on the input for n steps, where n is an incrementing counter. 3. Execute the given check on the output. If the check p…

We both came up with nearly the same idea at nearly the same time (within one minute) - what are the odds of that? My solution is slightly different - to avoid the Halting Problem, you can use a distributed approach. You have a very large (but finite) number of processors that you pass your programs to.

"what are the odds of that?"

I'm not sure, maybe we should build an unbelievably inefficient program to calculate them.

Re: Bogo-bogosort

#15

Post by deletes »

mikeash wrote: post #11

This got me thinking about a more generalized approach to this sort of thing. Given a task where you can check completion somehow , you can then solve it using the following procedure: 1. Generate a random program. (This could be a Turing machine, bytecode, C source, whatever.) 2. Execute the program on the input for n steps, where n is an incrementing counter. 3. Execute the given check on the output. If the check p…

(Assuming the programs are of length n generated using random ascii characters 0-127, and the number n starts out at 1, and the next time around is 2, then 3, and so forth.)

We are splitting the programs generated this way into two piles.

First pile are all the programs that don't compile and all the programs that compile and don't rely on size of the array that we want to sort. A very small number of programs compile . As n grows larger the number of programs that compile grows smaller as the chance of a random character error grows larger factorially. As n goes to infinity the ratio of programs that don't compile to programs that do, becomes divergent; in other words: the number of programs that don't compile tends to infinity and programs that do compile tends to zero. Therefore we can assume every program in first pile is a program that doesn't compile.

The second pile are the programs that compile and actually rely on the size of the array. The complexity of these programs is dependent on their algorithm. We are assuming the worst case where every algorithm is of complexity O(n!).

But errors in the programs from second pile also grows factorially. So the number of programs in second pile compared to first also approaches zero as n goes to infinity.

Complexity of programs in the first pile, since they don't rely on the input( where input is the size of the array ), is constant. Where the constant is the number n( steps ).

As n tends to infinity the number of the seconds programs tends to zero and their complexity becomes negligible. Therefore the total complexity becomes either O(1) or O(inf).

If you choose the n to stop at a finite number, then the complexity of the program is O(1)

If you choose n never stop, to become infinite then the algorithm never ends.

Feel free to comment, please refer to specific parts of the solution.

edit: Complexity of programs that fails to compile, or compile and don't rely on the size of the array is O(1), since that specific program always executes in the same time as it takes no variable input that would change regarding to size of the array.

Re: Bogo-bogosort

#16

Post by mikeash »

deletes wrote: post #15
mikeash wrote: post #11

This got me thinking about a more generalized approach to this sort of thing. Given a task where you can check completion somehow , you can then solve it using the following procedure: 1. Generate a random program. (This could be a Turing machine, bytecode, C source, whatever.) 2. Execute the program on the input for n steps, where n is an incrementing counter. 3. Execute the given check on the output. If the check p…

(Assuming the programs are of length n generated using random ascii characters 0-127, and the number n starts out at 1, and the next time around is 2, then 3, and so forth.) We are splitting the programs generated this way into two piles. First pile are all the programs that don't compile and all the programs that compile and don't rely on size of the array that we want to sort. A very small number of programs compil…

> If you choose n to be a non-infinite number, then the complexity of the program is O(1) If you choose n to be infinite then the complexity is O(inf)

I'm not sure I understand this, or you've understood me. The number n starts out at 1, and the next time around is 2, then 3, and so forth.

Re: Bogo-bogosort

#17

Post by zardeh »

deletes wrote: post #3

My addition to the algorithm: Every time your check if arrays is sorted and it isn't, start from the very beginning throwing away all progress made so far. I doubt this way n == 6 would finish in some normal time period.

bogosort does that already.

I ran it on an the array [0,1,2,3,4,5,6] and it took between 3 hundred million and 1 billion operations (by my marginally accurate counter) and between 6 and 20 minutes, but mine was in python, not C.

Re: Bogo-bogosort

#18

Post by deletes »

mikeash wrote: post #16
deletes wrote: post #15

Earlier quoted context omitted.

(Assuming the programs are of length n generated using random ascii characters 0-127, and the number n starts out at 1, and the next time around is 2, then 3, and so forth.) We are splitting the programs generated this way into two piles. First pile are all the programs that don't compile and all the programs that compile and don't rely on size of the array that we want to sort. A very small number of programs compil…

> If you choose n to be a non-infinite number, then the complexity of the program is O(1) If you choose n to be infinite then the complexity is O(inf) I'm not sure I understand this, or you've understood me. The number n starts out at 1, and the next time around is 2, then 3, and so forth.

My explanation is not to be understood easily( that doesn't mean it is very clear( or good ) ). Your best bet here would probably be to study big-o notation(+math, function limits) and think of the solution for yourself( there definitely is one ), as it can become quickly confusing as to what are you measuring really.

Re: Bogo-bogosort

#19

Post by mikeash »

deletes wrote: post #18
mikeash wrote: post #16

Earlier quoted context omitted.

> If you choose n to be a non-infinite number, then the complexity of the program is O(1) If you choose n to be infinite then the complexity is O(inf) I'm not sure I understand this, or you've understood me. The number n starts out at 1, and the next time around is 2, then 3, and so forth.

My explanation is not to be understood easily( that doesn't mean it is very clear( or good ) ). Your best bet here would probably be to study big-o notation(+math, function limits) and think of the solution for yourself( there definitely is one ), as it can become quickly confusing as to what are you measuring really.

I understand big-O notation just fine. I asked a specific question about your post, and nothing that indicated I misunderstood the principle in general. You spoke of "choosing n" to be either infinite or non-infinite, which doesn't make sense to me given the algorithm I proposed.

Re: Bogo-bogosort

#20

Post by deletes »

mikeash wrote: post #19
deletes wrote: post #18

Earlier quoted context omitted.

My explanation is not to be understood easily( that doesn't mean it is very clear( or good ) ). Your best bet here would probably be to study big-o notation(+math, function limits) and think of the solution for yourself( there definitely is one ), as it can become quickly confusing as to what are you measuring really.

I understand big-O notation just fine. I asked a specific question about your post, and nothing that indicated I misunderstood the principle in general. You spoke of "choosing n" to be either infinite or non-infinite, which doesn't make sense to me given the algorithm I proposed.

I didn't explain that( was edited ), of course you start at with n at 1,2,3... and so forth. But you can decide when to stop, and so I made two cases.

Anyway; you gave me a good exercise to practice on. Thanks.

Post reply on HN