Is the set of all algorithms computable?

Question

Informally, I am basically asking if there is an algorithm that checks if the input is an algorithm or not.

In Proofs From the Inside Out by John Stillwell, the author sometimes talks about an enumeration for all algorithms $A_1, A_2, ...$ (e.g., section 4.3 page 76). (The author also does that without giving a formal definition of what an algorithm is!) This makes the set of all algorithms computably enumerable (as he is literally listing all algorithms one by one), and so my first instinct was to ask if such set is computable.

Initially I thought yes! But that would mean there is an algorithm $A'$ that checks if something is an algorithm or not. That already seems very weird. Assuming this is fine, we may run into the following issue: $A'$ must itself belong to the set of all algorithms, and so we would have to make $A'$ an input of $A'$. That is also strange, so I thought I come to StackExchange for some help.

Answer 1

This depends on the definition of "algorithms". If as stated informally in Wikipedia (often used in introductory algorithm courses),

Starting from an initial state and initial input (perhaps empty),the instructions describe a computation that, when executed, proceeds through a finite number of well-defined successive states, eventually producing "output" and terminating at a final ending state.

Then the answer is definitely no, because an algorithm that determines whether an input is an algorithm as above would be able to solve the halting problem.

However, if the definition of algorithms are essentially partial recursive functions, then definitely yes. To give a "proof", "algorithms" can be defined as well-formed C++ programs, then a C++ compiler (with minimal change to produce a boolean output instead of machine code and error messages) is an algorithm to determine whether an input text is an algorithm. Note that we can write a C++ compiler in C++, so the "C++ compiler" could be understood as a well-formed C++ program which is by our definition an algorithm.

As $A'$ can be made an input of $A'$, there is no surprise at all. If you write down a program $P$ that takes a string and returns a string with all empty spaces deleted, you can enter $P$ itself into $P$. This kind of self-reference (and more subtle ones) is frequently used in TCS, such as to show the halting problem is undecidable. If it makes you more comfortable, the execution of an algorithm (which might be understood as a physical process involving hardware) is different from an algorithm (a text).

For more fun, it was a famous challenge to write down a program that prints itself.

Answer 2

Following Turing’s insights and suggestions, it is reasonable to define an algorithm as a finite set of instructions as expressed using some finite expression (string) of some language with an enumerable alphabet. Since the set of all finite strings of an enumerable language is enumerable itself, it follows that the set of all algorithms as expressed by that language is enumerable.

Notice that this does not require that you can tell, given any expression from that language, whether that describes an algorithm or not. That depends on the exact definition of an algorithm as expressed in that language. In most practical cases, though, you can. For example, it’s straightforward to decide whether some string of symbols is a program in accordance to some specific programming language.