[shadowlight]

The algorithm that executes an element from the set of all algorithms one at a time until an algorithm succeeds to select an element from a set will work on any set and itself?

   a = the algorithm
   A = set of all selection algorithms
   b = any set

   def a(x):
       while True:
           f = a(A) # you have to select an algorithm from the set of selection algorithms
           result = f(x)
           if result is None:
             A = A - f # set of all selection algorithms without f
             continue
           else:
             return result

   a(b) #will always return a result or not terminate for any choice of b?

Obviously there's problems with this because I'm not a mathematician and I'm just making stuff up off the top of my head. But would any one who's an expert care to explain what's the issue with the above?

I'm looking at it and such an algorithm is defined in terms of itself (like a factorial, which is legal) and may never terminate (which also legal because an algorithm selecting the smallest number from all sets that only contain positive numbers will never terminate either).

Wait but then if you look at the code it provably will never terminate because A does not shrink as it recurses.

[ketralnis]

The assertion that at least one selection algorithm succeeds without presenting that algorithm _is_ the axiom of choice.

By _assuming_ that program terminates, you are yourself taking the axiom of choice.

If it _does_ terminate, then it's not an axiom anymore it's a proof.

[shadowlight]

Yeah, this clarifies the logic. So because the algo above doesn't terminate it is not a proof.

The axiom of choice is an assumption that is neither known to be true or false.

[rocqua]

I think that such an algorithm, if the order of algorirthms tried is random, is almost surely (so with probability 1) never going to terminate.

Moreover, you'd probably want to limit the tries to algorithms that terminate. But that brings you into the halting problem.

[openasocket]

You can run a countably infinite sequence of algorithms in parallel and stop when one of them terminates without running into the halting problem. Say you have a set of algorithms, numbered 1, 2, 3, ... and each algorithm consists of a sequence of instructions (with jumps and gotos), where each instruction takes a finite amount of time to run. The algorithm is as follows: run the first instruction for algorithm 1, then the next instruction for algorithm 1, then the instruction for algorithm 2, then 1 again, then 2, then 3, then 1, 2, 3, and 4, and you can see the pattern now. If any of them reaches the halt instruction halt. Even if all but one of these algorithms runs forever, you'll still eventually halt when that one algorithm completes. I believe this approach is called dove tailing

[shadowlight]

Can you iterate through a set without * selection *? I'm confused about this part. It seems to me in order to use an algorithm from the set of all algorithms you need to invoke the axiom itself.

I think us programmers think in terms of time. But in math there is no time so whether you do things in parallel or procedural is irrelevant. That's why you can discuss infinities in math.

[openasocket]

> It seems to me in order to use an algorithm from the set of all algorithms you need to invoke the axiom itself.

Nope, you don't need the axiom of choice to define the sequence of all algorithms. The axiom of choice allows you to order any arbitrary set, but you don't need it for things you can construct an explicit order for, like the natural numbers. In the case of all algorithms, it's somewhat straightforward to construct the set of all of them. You can construct the sequence of all strings, right? You can construct them as "", "a", "b", "c", ... "y", "z", "aa", "ab", ... "ay", "az", "ba", "bb", ... Now, pick a programming language, like C. Given any valid string, you can determine if it is a valid C program in finite time, and if so you can convert it into a set of instructions to use in the dove-tailing procedure in finite time. Take the list of all strings in the manner described above. For each one interpret it as a C program, or if it's got invalid syntax interpret it as a program that immediately halts. Now you've got an enumerable sequence of algorithms. Since C is Turing complete you'll find every single algorithm in that sequence. There will be a ton of duplicates (for whatever notion of equivalence you want to use) but all the algorithms will be there, and in a well-defined order that you can enumerate through.

[shadowlight]

>Nope, you don't need the axiom of choice to define the sequence of all algorithms.

No. I'm saying selecting an algorithm out of the set of all algorithms.

I'm not saying defining the set of all algorithms.

[rocqua]

Putting the set of all algorithms in an order is quite easy. Like the comment above suggests. Just put them in alphabetical / lexicographical order.

Then you don't need to "randomly pick" an algorithm. You just start with the first algorithm in the sequence, and keep going.

[Avshalom]

if the set of all selection algorithms is infinite you need the axiom of choice to guarantee that you can even select an algorithm from it.

[tshaddox]

Can’t the algorithms be enumerated? For example, you could take their source code and sort them alphabetically.

[shadowlight]

This is the weird fuzzy part with math.

I can say arbitrary stuff like the set of all sets with positive numbers but when I say the set of all algorithms written in English and C++ suddenly I'm getting too specific. Where is the line drawn?

[tshaddox]

I’m not sure what you mean. There’s nothing too specific about that.

[shadowlight]

Your assuming all algorithms are defined in terms of English that's how you can order them alphabetically. English is an arbitrary language that comes from human culture. Same with a programming language. You are defining a set in terms of concepts that are cultural.

Algorithms themselves have no specific order. In order to define enumeration you must first start off by *selecting* which algorithm gets the first enumeration. This is a completely arbitrary choice.

[tshaddox]

No, I'm not assuming any particular encoding of an algorithm. I'm just assuming by "algorithm" you mean a computable function, and we know there are only countably many computable functions. This is not a cultural notion.

And yes, which particular encoding you decide to use is arbitrary, but the point is that you can enumerate the set of all algorithms, and thus you can select one without needing the axiom of choice.

[shadowlight]

Yeah I think that's the problem.

[jaydaigle]

ketralnis is right that this only terminates if an algorithm exists, so the claim that this terminates is equivalent to the axiom of choice.

But I'd also add that you can have a choice function that isn't an "algorithm". An algorithm, at least in the sense I'd generally interpret the word, has finitely many instructions and at most countably many steps. If we have uncountably infinitely many uncountably infinite sets, it is possible to have a choice function that can't be described in a finite algorithm.

Like, think about a well-ordering of the reals. If you believe the axiom of choice, then one exists. But you can't tell me what it is, because that would involve handing me infinite amounts of information. And similarly you can't write down an algorithm to produce it, without writing down infinite amounts of data.

[shadowlight]

> ketralnis is right that this only terminates if an algorithm exists, so the claim that this terminates is equivalent to the axiom of choice.

No my algorithm above will never terminate. There's a recursive call where the input never shrinks and it won't converge on a base case.

It's equivalent to saying

   def f(x):
       return f(x)

which is a pointless (but true) statement. The whole thing is distracting everyone.

Basically ketralnis is clarifying context which is sort of lost with my post. There's an axiom and do you believe in the axiom of not?

If the axiom can be proven then it is not an axiom. But a theorem. What I'm doing here is kind of pointless because we know it's an axiom by definition, the question is whether this axiom is valid or not. Attempting to prove the axiom is a a signal that I'm lacking clarity with the logic here.

[shadowlight]

So to simplify basically the algorithm I wrote above is bad because it's in spirit equivalent to this:

  def a(x):
      return a(x)