5 ms·

From a mathematical view on complexity, I don't see exactly the difference between memory and computation. I wonder what would be suitable definitions for the t

From a mathematical view on complexity, I don't see exactly the difference between memory and computation. I wonder what would be suitable definitions for the two concepts.

shele 7y ago
You can make sense of the differences abstractly considering the band, the state register and the instruction table of a Turing machine.
- jacquesm 7y ago
  A Turing machine is just one of many ways in which you could make a computing device. It is one of the easiest to mechanize and program for, which is why we use them but there is absolutely no reason to believe it is the only way of doing things. GP was getting at a more basic form of computation than the specific one performed by Turing machines. From a mathematical perspective the tape, the registers and instruction tables are all implementation details.
  - shele 7y ago
    > absolutely no reason to believe it is the only way of doing things Well, I did not suggests that. > From a mathematical perspective the tape, the registers and instruction tables are all implementation details. No, they are used to define concepts such as space complexity for Turing machines and there is something to learn from Turing machines, that's why people are studying them.
    - pdpi 7y ago
      You can think of the Church Turing thesis as providing a formalism for how the tape, registers and instruction tables are all implementation details.
- mikorym 7y ago
  So the band and state register is memory? And the instruction table is computation?
  - gpm 7y ago
    The instruction table is a function. Computation is the act of applying that function to the state. Edit: Grammatically "computation" is "The act of computing" where computing is a verb. "Memory" is a noun, and not one about an act. It's more like saying "clothing".
    - mikorym 7y ago
      This kind of touches on my original point. A function can be seen both as the set of all pairs of the function, or as an oracle that you feed input to and receive output. The first is to me the full memory space, the second is maybe computation.
wongarsu 7y ago
Memory is the current state, computation is the permutation of state (your step function that takes you from one state to the next).
- mikorym 7y ago
  This is assuming you have an automaton, I would guess? But what if you approach it via something like entropy? Edit: Doesn't that step function encode all of memory implicitly?
  - gpm 7y ago
    I have no clue what you mean by approaching computation from the point of view of entropy, entropy is a measure of the degree of disorder in a system, how is that a method of performing computation? The step function does not encode memory. The step function is a function that takes memory state 1 as input, and outputs memory state 2 as output. The step function itself doesn't change, it stores no information. In physical terms, the step function is the CPU, minus the caches, registers and other modifiable state. Memory is the disk and ram and all the CPUs caches and registers. You can't tell me anything about what the input to the CPU is, or what it is actually doing (other than that it is capable of running arbitrary x64 assembly), without looking at the state.
    - mikorym 7y ago
      A function does store information. The common definition of a function is the set (R,(X,Y)) where R is the graph of the function (consisting of the pairs) and X and Y are domain and codomain, respectively. Computation can be seen as some act of carrying out logic. And in turn, logic can be approached via entropy. There are a lot of people working in QM, computation and entropy. But the simpler definition is just via partitions (and you especially don't have to insist on it being in the world of QM either). [1] [1] http://www.ellerman.org/intro-logical-entropy/ http://www.ellerman.org/intro-logical-entropy/
      - gpm 7y ago
tel 7y ago
If computation is the process of spending effort to receive information, then memory is partially paid-down computation. There are lots of ways to blur these lines.
arcticbull 7y ago
This is actually reflected in modern FPGA devices. To your point, there's no material difference between "computation" and "retrieval" (they're just two different ways of mapping a set of inputs onto a set of outputs). FPGAs [1] are basically giant arrays of truth tables. These are implemented as look-up tables -- RAM -- paired with some dedicated, optimized, high-complexity logic elements like multipliers. Could you implement a 16x16 bit multiplier (yielding a 32-bit result) as a RAM or ROM, I mean, totally. It would be a 32 bit address space where each entry is also 32 bits. That would take 16GB. You'd have the fastest multiplier in the West, though, net of propagation delay. [1] From a combinational logic perspective.

From a mathematical view on complexity, I don't see exactly the difference between memory and computation. I wonder what would be suitable definitions for the two concepts.

shele 7y ago

You can make sense of the differences abstractly considering the band, the state register and the instruction table of a Turing machine.

jacquesm 7y ago
A Turing machine is just one of many ways in which you could make a computing device. It is one of the easiest to mechanize and program for, which is why we use them but there is absolutely no reason to believe it is the only way of doing things. GP was getting at a more basic form of computation than the specific one performed by Turing machines. From a mathematical perspective the tape, the registers and instruction tables are all implementation details.
- shele 7y ago
  > absolutely no reason to believe it is the only way of doing things Well, I did not suggests that. > From a mathematical perspective the tape, the registers and instruction tables are all implementation details. No, they are used to define concepts such as space complexity for Turing machines and there is something to learn from Turing machines, that's why people are studying them.
  - pdpi 7y ago
    You can think of the Church Turing thesis as providing a formalism for how the tape, registers and instruction tables are all implementation details.
mikorym 7y ago
So the band and state register is memory? And the instruction table is computation?
- gpm 7y ago
  The instruction table is a function. Computation is the act of applying that function to the state. Edit: Grammatically "computation" is "The act of computing" where computing is a verb. "Memory" is a noun, and not one about an act. It's more like saying "clothing".
  - mikorym 7y ago
    This kind of touches on my original point. A function can be seen both as the set of all pairs of the function, or as an oracle that you feed input to and receive output. The first is to me the full memory space, the second is maybe computation.

wongarsu 7y ago

Memory is the current state, computation is the permutation of state (your step function that takes you from one state to the next).

mikorym 7y ago
This is assuming you have an automaton, I would guess? But what if you approach it via something like entropy? Edit: Doesn't that step function encode all of memory implicitly?
- gpm 7y ago
  I have no clue what you mean by approaching computation from the point of view of entropy, entropy is a measure of the degree of disorder in a system, how is that a method of performing computation? The step function does not encode memory. The step function is a function that takes memory state 1 as input, and outputs memory state 2 as output. The step function itself doesn't change, it stores no information. In physical terms, the step function is the CPU, minus the caches, registers and other modifiable state. Memory is the disk and ram and all the CPUs caches and registers. You can't tell me anything about what the input to the CPU is, or what it is actually doing (other than that it is capable of running arbitrary x64 assembly), without looking at the state.
  - mikorym 7y ago
    A function does store information. The common definition of a function is the set (R,(X,Y)) where R is the graph of the function (consisting of the pairs) and X and Y are domain and codomain, respectively. Computation can be seen as some act of carrying out logic. And in turn, logic can be approached via entropy. There are a lot of people working in QM, computation and entropy. But the simpler definition is just via partitions (and you especially don't have to insist on it being in the world of QM either). [1] [1] http://www.ellerman.org/intro-logical-entropy/ http://www.ellerman.org/intro-logical-entropy/
    - gpm 7y ago

tel 7y ago

If computation is the process of spending effort to receive information, then memory is partially paid-down computation. There are lots of ways to blur these lines.

arcticbull 7y ago

This is actually reflected in modern FPGA devices. To your point, there's no material difference between "computation" and "retrieval" (they're just two different ways of mapping a set of inputs onto a set of outputs). FPGAs [1] are basically giant arrays of truth tables. These are implemented as look-up tables -- RAM -- paired with some dedicated, optimized, high-complexity logic elements like multipliers. Could you implement a 16x16 bit multiplier (yielding a 32-bit result) as a RAM or ROM, I mean, totally. It would be a 32 bit address space where each entry is also 32 bits. That would take 16GB. You'd have the fastest multiplier in the West, though, net of propagation delay. [1] From a combinational logic perspective.