Functions are an important concept for understanding the world, however the word "function" is slippery and ambiguous

Sometimes when people talk about "functions" they are talking about abstract processes that can be instantiated in the real world, other times they are talking about the properties of things that make them fit for some purpose. Other times they mean something else entirely - for example mathematical structure for mapping inputs to unique outputs.

In general, many words in natural language are ambiguous. When you are using an ambiguous word but want to talk about just one of its meanings it can help to explicitly set aside some different things that word can mean before diving into the meaning you actually want to discuss.

Wikipedia deals with this by having dedicated "disambiguation" pages, with links to them at the top of many other entries. My favourite such page is disambiguation (disambiguation).

This is a blog post about disambiguating the word "function"¹.

Functions are an important concept

I'm personally interested in functions for two main reasons.

Firstly, many things that matter to me seem to be easier to understand when you think about them in terms of the kinds of functions they are instantiating and how. To give two examples:

1. One way of thinking about musical compositions is that they are more than just their score, or any particular performance of that score³, but rather are a function you can give a performer or performers to instantiate in a given moment. Performers can tweak various parameters to make the piece of music their own ⁴.

2. My current view on the philosophy of consciousness is that human minds in this world are conscious in virtue of the functional properties they instantiate ⁵. However I mean this in a very particular sense of “functional”, which neither means “purpose” nor “in terms of input/output relations”.

These probably aren't the best examples to introduce the concept to a new reader, however they are the ones I find personally the most motivating. If it’s your first time encountering this topic you might like to first look at some more standard examples like mousetraps and heating systems. (The linked page is also a good example of a text which uses “function” ambiguously throughout ²).

Secondly, many innovations in the intersection of computer science and philosophy have come from progressively clarifying our understanding of functions, their limits, and the ways in which they relate to one another. Examples include: computability, decidability, reductions, complexity and types.

The word "function" is slippery and ambiguous

Functions and related concepts like "functional properties", or "being functionally identical" and so on seem like incredibly elegant things until you try to actually pin down some concrete examples. The paradigm example is normally the case of computer programs. But even clearly deploying these concepts in the case of computer programs is slippery and frustrating.

Take for example the following C program which prints a 12x12 multiplication table:

int main(void)
{
    int i, j, n = 12;

    for (j = 1; j <= n; j++) printf("%3d%c", j, j != n ? ' ' : '\n');
    for (j = 0; j <= n; j++) printf(j != n ? "----" : "+\n");

    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++)
            printf(j < i ? "    " : "%3d ", i * j);
                printf("| %d\n", i);
        }

    return 0;
}

I got this program from the beautiful website Rosetta Code - which helpfully lists 132 more programs in 132 different programming languages all doing the same thing.

This program performs some function. Are all the 132 other programs all performing the same function?⁶ Let's consider a number of ways in which they are, and are not.

For a start: some of these programs output exactly the same text, while others do not. This is all down to variations in formatting. For example the output of the C program looks like this:

  1   2   3   4   5   6   7   8   9  10  11  12
------------------------------------------------+
  1   2   3   4   5   6   7   8   9  10  11  12 | 1
      4   6   8  10  12  14  16  18  20  22  24 | 2
          9  12  15  18  21  24  27  30  33  36 | 3
             16  20  24  28  32  36  40  44  48 | 4
                 25  30  35  40  45  50  55  60 | 5
                     36  42  48  54  60  66  72 | 6
                         49  56  63  70  77  84 | 7
                             64  72  80  88  96 | 8
                                 81  90  99 108 | 9
                                    100 110 120 | 10
                                        121 132 | 11
                                            144 | 12

While the output of the C++ program looks like this:

       1   2   3   4   5   6   7   8   9  10  11  12

   1   1   2   3   4   5   6   7   8   9  10  11  12

   2       4   6   8  10  12  14  16  18  20  22  24

   3           9  12  15  18  21  24  27  30  33  36

   4              16  20  24  28  32  36  40  44  48

   5                  25  30  35  40  45  50  55  60

   6                      36  42  48  54  60  66  72

   7                          49  56  63  70  77  84

   8                              64  72  80  88  96

   9                                  81  90  99 108

  10                                     100 110 120

  11                                         121 132

  12                                             144

Both programs successfully solve the same task, and if you wanted to use their output tables for the purposes of looking up the answer to (for example) 11x12, either table would do, and you would get the same answer. You might say that these programs are "functionally identical" in the sense that they can be used for the same practical purposes.

However, its not the case that you could safely replace one of these programs with the other in any functional context and expect to get the same results. For example, if you are printing the output on paper, you might need more paper to print the output of the C++ program. If your printer can only print alphanumeric characters, then your C program may crash the printer when it outputs a "+" or a "-".

Teleological identity

This first example might feel like nitpicking, after all, the original task was to "print a 12x12 multiplication table", and it did not specify any particular format in which to do so. In any case, you can pretty trivially make small changes to one program or the other in order to make their outputs match. However I think it helps draw out a key point - which is that "print a 12x12 multiplication table" was somewhat of an ambiguous task in the first place. If the purpose of these tables is to be read by humans then either format will do just as well. With respect to this purpose the two programs are functionally identical.

There is already a word in philosophy which is used to describe things in terms of their purposes and that word is "teleological". You might say then that these two programs are teleologically identical. Biologists and philosophers of biology sometimes use the words "functional" and "teleological" interchangeably. For example you might say that the definition of an "eye" as a sense organ is teleological. Something is an eye if it can be used for the purpose of seeing. As a result, both human eyes and octopus eyes alike are functionally "eyes" in this teleological sense even though you can't literally graft an octopus eye onto a human's visual cortex and expect it to work. Their status as "eyes" is both dependent on what they are used for, but also on who, or what is using them.

Let's set aside the teleological sense for now, and consider other ways in which two things might or might not be performing the same function.

Input/output (set-theoretic) identity

The mathematical definition of a function is pretty straightforward: a function is a relation between a set of inputs and set of outputs such that every input maps to one and only one output (however multiple inputs can all map to the same output).

This can be thought of as an extensional definition, because it does not care how that mapping is defined or described, it only speaks about its ultimate results.

Under this definition two functions f and g are identical if and only if f(x) = g(x) - for all inputs x in some domain.

This is the kind of nice, precise, neat definition you get to use when you do math.

The problem with this definition is that while it captures perfectly and precisely what functions do it is entirely blind to how they do it. Consider another C program:

#include <stdio.h>

int main(void)
{
    printf("  1   2   3   4   5   6   7   8   9  10  11  12\n");
    printf("------------------------------------------------+\n");
    printf("  1   2   3   4   5   6   7   8   9  10  11  12 | 1\n");
    printf("      4   6   8  10  12  14  16  18  20  22  24 | 2\n");
    printf("          9  12  15  18  21  24  27  30  33  36 | 3\n");
    printf("             16  20  24  28  32  36  40  44  48 | 4\n");
    printf("                 25  30  35  40  45  50  55  60 | 5\n");
    printf("                     36  42  48  54  60  66  72 | 6\n");
    printf("                         49  56  63  70  77  84 | 7\n");
    printf("                             64  72  80  88  96 | 8\n");
    printf("                                 81  90  99 108 | 9\n");
    printf("                                    100 110 120 | 10\n");
    printf("                                        121 132 | 11\n");
    printf("                                            144 | 12\n");

    return 0;
}

In some ways this program is quite clever, in others it is quite silly. It is quite clever because it produces the 12x12 multiplication table without having to do any multiplication, or really any arithmetic at all. It just prints the lines of the table one by one. It is quite silly for the same reason.

Is this program functionally identical to the other program above? In both the teleological and set-theoretic senses, it is ⁷, but in terms of what computations it is actually performing it has more in common with the classic "hello, world" program than with producing multiplication tables.

In part 2 of this post I will talk about two other things we could mean when talking about "functions": causal networks of machine states, and complexity classes.