4 ms·

I’m aware the state you were talking includes state of all threads. When you combine several sequences of state transitions (one sequence per thread), you don’

I’m aware the state you were talking includes state of all threads. When you combine several sequences of state transitions (one sequence per thread), you don’t get another sequence of state transitions. When two CPU cores perform two state transitions at the same time, you typically cannot determine whichever of those transitions happened first. We might have different definitions what’s sequence. I mean this: https://en.wikipedia.org/wiki/Sequence https://en.wikipedia.org/wiki/Sequence As you see, global order is required for bunch of elements (in this case, state transitions) to form a sequence. And in concurrent and especially parallel programming, there’s no global order for those transitions. Hence, those transitions don’t form a sequence.

argv_empty 10y ago
No, we just have different notions of system state. If we have a pair of, say, Turing machine heads on one tape that aren't necessarily moving in lockstep, I say that the system state is the tape contents, the two heads' locations, and the two heads' states. A transition for this system can be either or both heads moving either direction, overwriting the symbol they're pointing at, and changing its own internal state. The state {tape="000111000", head0loc=0, head0state=2, head1loc=4, head1state=6} might transition to {tape="000101000", head0loc=0, head0state=2, head1loc=5, head1state=2}, or it might transition to {tape="100111000", head0loc=1, head0state=2, head1loc=4, head1state=6}, or to {tape="100101000", head0loc=1, head0state=2, head1loc=5, head1state=2}. In a given run of the system, one of those is what actually happens. Then another happens after that, and so on. So we get a sequence of them. A transition is not one machine head changing its position and state. {head0loc=0, head0state=2}->{head0loc=1, head0state=2} is not a transition because that does not identify a pair of whole-system states.
- Const-me 10y ago
  > one of those is what actually happens No it’s not. If the heads aren’t moving in lockstep, what actually happens is you’ll extremely rarely have a moment of time when both locations are whole numbers. At one moment you have { head1loc=0, head2loc=4.17 }, head #1 reached the cell position on the tape, head #2 is still moving. After a while, you’ll have { head1loc=0.872, head2loc=5}, head #1 is on its way, head #2 reached the cell position. Looks like for a Turing machine with two asynchronously moving heads, there’s no usable concept of “state” at all. That’s very close to what happens when doing actual parallel programming on real hardware. Good luck applying your idea of computation as a sequence of state transitions to that.
  - argv_empty 10y ago
    Even if a Turing machine were a physical object (I had thought you would be aware that it's not), either one of those moves completes before the other, or both complete simultaneously.
    - Const-me 10y ago
      Sure, it’s an abstract machine invented to research mathematical model of computation. I’d like to point out, the very moment you hooked second asynchronously moving head to the machine, the abstraction leaked spectacularly. With two asynchronous heads, the machine no longer has state; suddenly we need to consider physical time, not just count steps; and so on. Turing machine is useful abstraction for sequential computing, but nearly useless to research parallel computing problems. The same happens with many other abstractions and approaches when going parallel. > either one of those moves completes before the other Yeah, but in parallel computing, we don’t know that order, and have no way of knowing. Meaning the “sequence of state transitions” idea is IMO nearly useless.
    - dogecoinbase 10y ago
      if a Turing machine were a physical object ... either one of those moves completes before the other, or both complete simultaneously. ...depending on how fast you're moving relative to the machine heads and in what direction. Simultaneity does not exist in the real world.
      - argv_empty 10y ago
        We use the tape's reference frame, of course! Looking at data stored on some particular device in the physical system is going to force a particular reference frame, where you will have a defined simultaneity. A global definition of simultaneity is only really needed if your system promises to provide sequential consistency.
  - arielb1 10y ago
    Pick a reference frame. Sample the state of each CPU on its clock edge. Now you have a sequence of transitions. The sequence is heavily non-deterministic, but that's life in a concurrent universe.

argv_empty 10y ago

No, we just have different notions of system state. If we have a pair of, say, Turing machine heads on one tape that aren't necessarily moving in lockstep, I say that the system state is the tape contents, the two heads' locations, and the two heads' states. A transition for this system can be either or both heads moving either direction, overwriting the symbol they're pointing at, and changing its own internal state. The state {tape="000111000", head0loc=0, head0state=2, head1loc=4, head1state=6} might transition to {tape="000101000", head0loc=0, head0state=2, head1loc=5, head1state=2}, or it might transition to {tape="100111000", head0loc=1, head0state=2, head1loc=4, head1state=6}, or to {tape="100101000", head0loc=1, head0state=2, head1loc=5, head1state=2}. In a given run of the system, one of those is what actually happens. Then another happens after that, and so on. So we get a sequence of them. A transition is not one machine head changing its position and state. {head0loc=0, head0state=2}->{head0loc=1, head0state=2} is not a transition because that does not identify a pair of whole-system states.

Const-me 10y ago
> one of those is what actually happens No it’s not. If the heads aren’t moving in lockstep, what actually happens is you’ll extremely rarely have a moment of time when both locations are whole numbers. At one moment you have { head1loc=0, head2loc=4.17 }, head #1 reached the cell position on the tape, head #2 is still moving. After a while, you’ll have { head1loc=0.872, head2loc=5}, head #1 is on its way, head #2 reached the cell position. Looks like for a Turing machine with two asynchronously moving heads, there’s no usable concept of “state” at all. That’s very close to what happens when doing actual parallel programming on real hardware. Good luck applying your idea of computation as a sequence of state transitions to that.
- argv_empty 10y ago
  Even if a Turing machine were a physical object (I had thought you would be aware that it's not), either one of those moves completes before the other, or both complete simultaneously.
  - Const-me 10y ago
    Sure, it’s an abstract machine invented to research mathematical model of computation. I’d like to point out, the very moment you hooked second asynchronously moving head to the machine, the abstraction leaked spectacularly. With two asynchronous heads, the machine no longer has state; suddenly we need to consider physical time, not just count steps; and so on. Turing machine is useful abstraction for sequential computing, but nearly useless to research parallel computing problems. The same happens with many other abstractions and approaches when going parallel. > either one of those moves completes before the other Yeah, but in parallel computing, we don’t know that order, and have no way of knowing. Meaning the “sequence of state transitions” idea is IMO nearly useless.
  - dogecoinbase 10y ago
    if a Turing machine were a physical object ... either one of those moves completes before the other, or both complete simultaneously. ...depending on how fast you're moving relative to the machine heads and in what direction. Simultaneity does not exist in the real world.
    - argv_empty 10y ago
      We use the tape's reference frame, of course! Looking at data stored on some particular device in the physical system is going to force a particular reference frame, where you will have a defined simultaneity. A global definition of simultaneity is only really needed if your system promises to provide sequential consistency.
- arielb1 10y ago
  Pick a reference frame. Sample the state of each CPU on its clock edge. Now you have a sequence of transitions. The sequence is heavily non-deterministic, but that's life in a concurrent universe.