[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.

[shadowlight]

As my retort to that common mentioned, he is wrong.

That is still random. You are arbitrarily picking an encoding, (English) in this case. Why not a Russian programming language or Chinese? How did you *select* your encoding out of the set of all encodings?

The act of assigning order to an unordered set is arbitrary. ABC order is a made up concept. It's not numerical, it's an arbitrary language and an arbitrary order that's a by product of human culture. Thus invoking this is at it's essence invoking the axiom of choice. You are arbitrarily selecting an algorithm.

[myWindoonn]

Gödel worried about this, and one of the lemmas leading up to their First Incompleteness theorem is that the encoding doesn't matter, as long as it's a bijection on valid algorithms. (Numbers which code for invalid algorithms, perhaps due to syntax errors, can be ignored.) Gödel also was the one who showed that such encodings are possible and useful in the first place, so the problem of arbitrary encodings started and ended with him.

You can phrase things like Gödel did. For any encoding of algorithms into natural numbers which is bijective (ignoring invalid syntax), enumerate the algorithms as 0, 1, 2, 3, ... using the bijection, and then run them in parallel by taking steps [0, 0, 1, 0, 1, 2, 0, 1, 2, 3, ...] The user provides an encoding, without invoking the Axiom of Choice.

[openasocket]

I think you're misunderstanding the axiom of choice, focusing too much on the literal word "choice". Sure, that ABC order is arbitrary, but so are most mathematical constructions! How did I "select" that encoding? By defining it! By your definition of the axiom of choice, literally defining any set at all (besides the null set and the set of natural numbers, which are defined in their own axioms) would require invoking the axiom of choice.

You only need the axiom of choice if you need to pick an element out of a set WITHOUT SPECIFYING which one you are picking. And sometimes not even then. For instance, if you want to prove all elements in a set have a certain property, often you will see proofs take the form "pick an element of that set, assume it doesn't have this property, then by X, Y, and Z we have a contradiction, thus all elements have that property". That doesn't involve the axiom of choice at all, even though a straight reading of that statement makes it sounds like we are making a choice. In truth that proof is saying we can do this with every single element of that set, so you aren't really making a "choice". You only need the axiom of choice when you are, say, stating the existence of a function without defining what that function is. For an example of an actual invocation of the axiom of choice, check out the proof sketch in the wikipedia article on Zorn's Lemma: https://en.wikipedia.org/wiki/Zorn%27s_lemma .