While working on developing a tic tac toe AI, I realized that I had encountered a concrete example of something that could not be represented using a linear function.

When you are doing regression, you usually start out by coming up with a generic function that has the capacity to somewhat accurately describe the relationship between the several variables of an input and the resulting output.

The easiest relationship to work with is linear1. We can just assume that the output is some linear combination of the input variables. We just have to find the weights of the variables that will best fit our available data (training examples).

But if your inputs are tightly coupled, meaning

the effect that one of your variables has on the output depends on the value of another,

you cannot accurately represent the system with a linear function. Your output might be the product of your input variables, e.g. $output = x_1 * x_2 * x_3 * ...$.

Imagine trying to represent the area of a rectangle (which is a function of height and width) with a linear function!

There are simply no weights $w_1$ and $w_2$ that could make this happen. This system is simply not linear. The relationship between the inputs (width and height) and the output (area) is not linear. The inputs are tightly coupled. They have a synergistic effect on the output.

1. Linear functions are easy to solve and differentiate/integrate. We have developed tons of mathematical (analytical and numerical) methods to deal with them.