Deep learning combines linear functions together, but the way in which they are combined is always nonlinear. If the way in which they were combined were linear, the resulting function would also be linear (a linear combination of linear functions is linear), and you'd have linear regression. Specifically the final layer of a deep neural network is often linear but the nodes in middle layers are often Rectified Linear Units which have a nonlinear "max" function applied to a linear function. Without these "max" functions you'd be able to flatten all the layers into one. Other common nonlinear functions you'll find in a deep neural net are sigmoid functions like tanh. These functions are sometimes called "activation functions".

Yes, there is a non-linear function between each linear function. The alternating back and forth between linear and non-linear is important.

Deep learning uses non-linear parts. And if by "the binary functions at the heart of CPUs", you mean elementary Boolean operations, then those aren't linear either.

Many logical operations that are foundational are non-linear (AND, NAND, NOR).

Here are a couple ways to look at the problem.

First, we should probably be more explicit about what we mean by "combine." The result of a computer's computation is some _composition_ of its fundamental operations. If all those operations are linear, the composition must be linear (let h(x)=f(g(x)) be finite-dimensional linear functions, then f(x)=Ax and g(x)=Bx for some matrices A,B, and you can verify that h(x)=(AB)x -- i.e., h is linear -- then you can chain that result together for any finite number of compositions to show that any halting program is linear).

The links you gave require a different definition of combination from composition. Yes, nice enough functions can be _locally_ approximated by lines, but those lines aren't composed to give the final result; they're spliced together piecewise, and that splicing operation is nonlinear. If your computer's fundamental operations are all linear then that splicing operation can't be implemented, so the whole nonlinear combination can't be implemented either.

To the other evidence (deep learning, binary functions), the apparent contradiction arises because neither deep learning nor binary functions are inherently linear:

Deep learning does have large linear components (partly from a virtuous cycle of linear stuff being easy to compute and analyze, then hardware being designed to implement linear stuff more efficiently resulting in the status quo where there's a huge body of knowledge/software/hardware making large linear components the easy path to good results in a lot of cases), but critically they also have small nonlinear portions that enable them to approximate any nice enough function, not just the linear ones (if you want to look it up further, introductory search terms include "activation function", "rectified linear activation unit", and "sigmoid").

For the binary function example you can get away with a counting argument to show that OR isn't linear for any valid definitions of addition (i.e., they form groups) over 1-bit and 2-bit elements (even weird ones like assuming 2-bit elements add together like the klein 4-group):

- Pick a 3/1 unbalanced binary function like OR (which maps three 2-bit elements to 1 and one of them to 0).

- In the 4x4 table of all possible combinations of f(a+b) you'll have 12 1s and 4 0s.

- In the 4x4 table of all possible combinations of f(a)+f(b) you'll have 6 of either 1 or 0 and 10 of the other.

- 12,4 equals neither 6,10 nor 10,6, so the two tables aren't equal. We conclude that f(a+b)!=f(a)+f(b) for some 2-bit elements a,b.

- Hence, OR isn't linear (and neither are AND, Implies, ImpliedBy, and their negations by similar logic).

Awesome. Really appreciate the clear edification. All the replies have been really useful. Thanks!