5 ms·

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

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...

wiml 5y ago
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).
- tines 5y ago
  Is nand nonlinear?
  - drdeca 5y ago
    Yes
  - tromp 5y ago
    Yes, since it's nonzero on zero inputs, while a linear function satisfies f(0,0) = f(0 * (x,y)) = 0 * f(x,y) = 0.
- deleted 5y ago
  [deleted]
- vlovich123 5y ago
  Can you expand on that point a bit? 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. https://mathinsight.org/approximating_nonlinear_function_by_linear https://mathinsight.org/approximating_nonlinear_function_by_... https://en.m.wikipedia.org/wiki/Linearization https://en.m.wikipedia.org/wiki/Linearization https://stackoverflow.com/questions/4908893/what-logic-gates-are-required-for-turing-completeness#4909412 https://stackoverflow.com/questions/4908893/what-logic-gates...
  - jhgb 5y ago
    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.
  - WORLD_ENDS_SOON 5y ago
    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".
    - Buttons840 5y ago
      Yes, there is a non-linear function between each linear function. The alternating back and forth between linear and non-linear is important.
  - TrueDuality 5y ago
    Many logical operations that are foundational are non-linear (AND, NAND, NOR).
  - hansvm 5y ago
    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).
- ajb 5y ago
  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 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.
  - deleted 5y ago
    [deleted]
  - jhgb 5y ago
    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).
    - ajb 5y ago
      A reversible function can do all the work of any given irreversible function. Specifically, supposed your reversible function is G(x). a reversible function for this is then (X, Y) => (X, G(X) ^ Y)
      - jhgb 5y ago
        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.
Buttons840 5y ago
> 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.
- Buttons840 5y ago
  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.
ac42 5y ago
> 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.

wiml 5y ago

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).

tines 5y ago
Is nand nonlinear?
- drdeca 5y ago
  Yes
- tromp 5y ago
  Yes, since it's nonzero on zero inputs, while a linear function satisfies f(0,0) = f(0 * (x,y)) = 0 * f(x,y) = 0.
deleted 5y ago
[deleted]
vlovich123 5y ago
Can you expand on that point a bit? 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. https://mathinsight.org/approximating_nonlinear_function_by_linear https://mathinsight.org/approximating_nonlinear_function_by_... https://en.m.wikipedia.org/wiki/Linearization https://en.m.wikipedia.org/wiki/Linearization https://stackoverflow.com/questions/4908893/what-logic-gates-are-required-for-turing-completeness#4909412 https://stackoverflow.com/questions/4908893/what-logic-gates...
- jhgb 5y ago
  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.
- WORLD_ENDS_SOON 5y ago
  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".
  - Buttons840 5y ago
    Yes, there is a non-linear function between each linear function. The alternating back and forth between linear and non-linear is important.
- TrueDuality 5y ago
  Many logical operations that are foundational are non-linear (AND, NAND, NOR).
- hansvm 5y ago
  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).
ajb 5y ago
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 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.
- deleted 5y ago
  [deleted]
- jhgb 5y ago
  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).
  - ajb 5y ago
    A reversible function can do all the work of any given irreversible function. Specifically, supposed your reversible function is G(x). a reversible function for this is then (X, Y) => (X, G(X) ^ Y)
    - jhgb 5y ago
      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.

Buttons840 5y ago

> 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.

Buttons840 5y ago
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.

ac42 5y ago

> 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.