Would it be possible to develop a computer from linear transformations? Suppose registers, op codes and their parameters were represented as images, and at each clock a led grid is turned on with the current computer state, the light propagating into a sequence of diffractive surfaces to generate the next state through linear transformations, which is picked up and its result is used to change the led grid in the right places. Even if such a thing could be turing complete I guess the current computing problem is memory retrieval time and not internal cpu processing time...
You really need some nonlinear functions if you want to compute interesting things (and you can't build nonlinear functions out of purely linear parts).
Deep learning approximates non-linear functions and the binary functions at the heart of CPUs are inherently linear no? That would seem to contradict the argument that you can’t build non linear functions out of linear parts. As a general concept, it seems generally possible to approximate non linear functions with linear ones, which I imagine is how deep learning works. I’m not a domain expert at any of these math topics though so happy to learn more.
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.
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".
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).
Actually, you can do logic in linear (matrix) operations. This is what quantum computers do. Eg, if you look at the toffoli gate: https://en.wikipedia.org/wiki/Toffoli_gate it's a universal logic function (any logic function can be constructed using it) but in its form as a permutation matrix, it's a linear matrix operation.
The catch is that its input is in the form of a vector having 1 entry for each possible value of the input in actual bits, which is an exponential increase in space. But, it is an existence proof that in some sense, you can do logic with linear functions, as long as you don't mind some kind of weird representation of your inputs and outputs.
What I don't know is, whether you can use linear operations for logic with a smaller than exponential space increase.
As far as I understand it, you can construct reversible functions this way, but many interesting functions are irreversible (for example an OCR process generates an ASCII string, but you can't reverse the process to get the original bitmap from the ASCII string).
And how do you get G(X) from (X, G(X) ^ Y), then? (I assume you meant "your irreversible function is G(x)"?) That sounds like "you can find a reversible component in an irreversible calculation", which is probably true, but maybe practically meaningless: You were yourself talking about "an exponential increase in space", but if I understood this Landauer limit thingy correctly, this also gives you an exponential limit in power dissipated.
That sounds to me like you're trying to cheat physics here. If there's a physical limit to calculating an irreversible G(X), I don't see how you magically remove it by pretending that something including G(X) is reversible and then by ignoring what you've just added.
What I'm trying to address is the claim that there is something 'interesting' about irreversible functions that you can't do using reversible functions. Irreversible functions just discard information in the course of calculating some value. You can simply save the discarded information and have the same calculated value in your result, and have a reversible function. Nothing about this violates physics. Obviously it's not exactly the same function - it has more outputs and inputs. But it can be used as a subcomponent of any operation where you needed the reversible function.
there is no such thing as a class of 'interesting' functions which cannot be used in this way.
A subtle factor is that for most interesting computations, the size of input and output you are interested in is much smaller than the size of temporary states required by the computation to produce that output.
It is useful to distinguish between the "middle" of a computation and "output stage".
Using irreversible computation, the middle requires a potentially large state, and a correspondingly large energy consumption.
You can often transform an irreversible computation to a reversible "middle", with an encoded result such that the "output stage" has to do projection and decoding, with that final step consuming energy, but not as much energy as the original irreversible computation would consume.
You do the computation while preserving every bit of information needed to run the whole computation backwards, then read just the output bits you want in the result, then run the middle computation backwards.
It's like compressing a spring and then accepting the energy back from the spring: That doesn't consume much energy, it just stores it and gives it back. A reversible computation is a very complicated spring, and you read the the output before letting it give back the energy from the reversible part.
As you can chain computations with "output" only at the end of the chain, it's useful to think of reversible, and maybe linear (e.g. one-shot encoded) computations as building blocks.
So I think Gravyness's question is a good, curious question, and there is something to it. Even though you can't build a complete, standard computer that way.
There are many practical and scaling obstacles. It has a lot in common with quantum computation (the ideal, theoretical version), though they are not the same thing. An (ideal, theoretical) quantum computation is linear and reversible, but on quantum states instead of classical states, and there is an energy-consuming input and output stage.
> Would it be possible to develop a computer from linear transformations?
No, a program consisting of a billion linear transformations could be simplified to a single linear transformation. The halting problem would be solved, all programs can halt. All calculations, no matter how many linear transformations they consist of, could be simplified to a single linear transformation. This would be absurdly good, but still absurd, thus impossible.
A key insight is that any combinations of linear transformations is a linear transformation. Got a sequence of a billion linear transformation? The entire sequence can be expressed as a single linear transformation. Thus, no matter how many linear transformation you perform, you're never able to exceed the abilities of a single linear transformation.
> Would it be possible to develop a computer from linear transformations?
Yes. The transition function of Turing machines and the working tape can be represented as linear transformations. For quantum computers, these transformations even need to be unitary.
This very standard construction does not conflict with the halting problem: you don't know how often you have to apply this linear transform to your state vector until you got your result.
The problem is the title, but remember that the researchers don't write the title of the press article.
It's well known that you can compute any desired linar transformation with light and lens, diffraction gratings and similar stuff. I've see people calculating the wavelets transform with a similar equipment, like 10 years ago.
The interesting part of the research article is that they got a better method to design the lens, diffraction gratings and similar stuff to calculate the transformation. This is somewhat explained in the article, but totally lost in the title.
Maybe you could have liquid crystals or other equivalent optical routing mechanisms. The pipeline can process billions of computations per second, but changing the pipeline takes milliseconds. Talk about SIMD...
For machine learning, an important nonlinear activation curve, the ReLU curve, seems like it might be achievable optically. Just bend the beam, and if it bends far enough, run it into something black.
They use the mirrors to do random projections very rapidly, and collecting the results on a CMOS receptor. Somehow the projection help tackle high-dimensional data.
Intro to how the math would be done at the beginning, meat of the device details at 20:10 :
https://youtu.be/0QtY4_UJF0w
Funny how you can do a mathematical projection using a projector!
36 comments
[ 3.1 ms ] story [ 86.3 ms ] threadDeep learning approximates non-linear functions and the binary functions at the heart of CPUs are inherently linear no? That would seem to contradict the argument that you can’t build non linear functions out of linear parts. As a general concept, it seems generally possible to approximate non linear functions with linear ones, which I imagine is how deep learning works. I’m not a domain expert at any of these math topics though so happy to learn more.
https://mathinsight.org/approximating_nonlinear_function_by_... https://en.m.wikipedia.org/wiki/Linearization https://stackoverflow.com/questions/4908893/what-logic-gates...
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).
The catch is that its input is in the form of a vector having 1 entry for each possible value of the input in actual bits, which is an exponential increase in space. But, it is an existence proof that in some sense, you can do logic with linear functions, as long as you don't mind some kind of weird representation of your inputs and outputs.
What I don't know is, whether you can use linear operations for logic with a smaller than exponential space increase.
Specifically, supposed your reversible function is G(x). a reversible function for this is then (X, Y) => (X, G(X) ^ Y)
It is useful to distinguish between the "middle" of a computation and "output stage".
Using irreversible computation, the middle requires a potentially large state, and a correspondingly large energy consumption.
You can often transform an irreversible computation to a reversible "middle", with an encoded result such that the "output stage" has to do projection and decoding, with that final step consuming energy, but not as much energy as the original irreversible computation would consume.
You do the computation while preserving every bit of information needed to run the whole computation backwards, then read just the output bits you want in the result, then run the middle computation backwards.
It's like compressing a spring and then accepting the energy back from the spring: That doesn't consume much energy, it just stores it and gives it back. A reversible computation is a very complicated spring, and you read the the output before letting it give back the energy from the reversible part.
As you can chain computations with "output" only at the end of the chain, it's useful to think of reversible, and maybe linear (e.g. one-shot encoded) computations as building blocks.
So I think Gravyness's question is a good, curious question, and there is something to it. Even though you can't build a complete, standard computer that way.
There are many practical and scaling obstacles. It has a lot in common with quantum computation (the ideal, theoretical version), though they are not the same thing. An (ideal, theoretical) quantum computation is linear and reversible, but on quantum states instead of classical states, and there is an energy-consuming input and output stage.
No, a program consisting of a billion linear transformations could be simplified to a single linear transformation. The halting problem would be solved, all programs can halt. All calculations, no matter how many linear transformations they consist of, could be simplified to a single linear transformation. This would be absurdly good, but still absurd, thus impossible.
Yes. The transition function of Turing machines and the working tape can be represented as linear transformations. For quantum computers, these transformations even need to be unitary.
This very standard construction does not conflict with the halting problem: you don't know how often you have to apply this linear transform to your state vector until you got your result.
This type of processing was being used in guidance systems of missiles in the 1980s.
It's well known that you can compute any desired linar transformation with light and lens, diffraction gratings and similar stuff. I've see people calculating the wavelets transform with a similar equipment, like 10 years ago.
The interesting part of the research article is that they got a better method to design the lens, diffraction gratings and similar stuff to calculate the transformation. This is somewhat explained in the article, but totally lost in the title.
(Which greatly reduces the number of applications of the technique)
For example, I was tought how this worked in satillite image analysis optical computers (e.g. Cold War tech) when getting my optics degree.
https://lighton.ai/publications/
They use the mirrors to do random projections very rapidly, and collecting the results on a CMOS receptor. Somehow the projection help tackle high-dimensional data.
Intro to how the math would be done at the beginning, meat of the device details at 20:10 : https://youtu.be/0QtY4_UJF0w
Funny how you can do a mathematical projection using a projector!