I think you also need some form of intermediate storage to be Turing complete.
Not that this example doesn't have intermediate storage... But I suspect you could create or discover a mechanism that is expressive enough to implement any chain of logic gates, but is incapable of expressing storage (can't even use the gates to implement a latch)
I'm also a little dubious of granting the "Truing complete" label to something that can't conditionally terminate (at minimum)
Maybe you can trick a video codec into looping forever without new key frames (in which case it can never terminate), but most likely this would need to be implemented unrolled, so always terminates after a fixed number of iterations.
It looks like you can only make "wires" that go down or to the right, so there's no way to connect up NANDs to make a latch or flip-flop (which would require wires going back up or to the left).
If you were limited to just a single frame of itra blocks, then yes. This would be an example of logic without storage.
Also quite limiting as wires could never cross.
But I was kinda jumping ahead and assuming VP8 allows you to mix and match intra and inter prediction modes within a single frame (and that inter prediction will feed into intra prediction... that might be a flawed assumption...)
Inter prediction should allow you to copy from any block on the previous frame, effetely creating unlimited length wires in any direction. This also makes the previous frame latched storage, without having to construct a latch from gates.
> Inter prediction should allow you to copy from any block on the previous frame, effetely creating unlimited length wires in any direction.
I think "going inter" just gives you a third "dimension" along which you can still only travel one way -- but you need bidirectional travel (outputs feeding back into inputs) to implement memory. It makes sense to me that bidirectional travel is not possible here, since it would necessitate some kind of "keep processing until convergence" that could (and often would) prevent the decoder from making progress.
> This also makes the previous frame latched storage, without having to construct a latch from gates.
This makes me think we have different ideas of what "latched storage" means. I think the block that you would call a "latch in the previous frame" is functionally no different from a block elsewhere on the current frame? I don't see how it could have the same "address" but store a different value over time, which is what I'd call the defining property of all "storage".
> I think "going inter" just gives you a third "dimension" along which you can still only travel one way
Essentially intra prediction gives you two half dimensions. The temporal aspect of inter prediction gives you a third half dimension (which we could just call time). I agree that three half dimensions is not enough.
But... intra prediction also has motion compensation, which is essentially two full spacial dimensions that are accessible as long as you are traveling along the time dimension. And apparently 2.5D is enough. [1]
I'm not sure how you can should add these dimensions together, but arguably we are talking about 3.5D, which should be way more than enough.
> This makes me think we have different ideas of what "latched storage" means.
True. The value latched at the end of the previous frame would arguably count as globally-clocked storage, not latched. It's just in regular electronics, you are using latched storage to build clocked storage, so I kind of saw clocked as a superset of latched.
Which might be true, I can't really see a reason why you couldn't construct a latch from globally-clocked storage generally (as long as you have already solved the problem of moving backwards). At least in this case it's trivial, you just move both inputs back towards the top-left of the next frame.
> I think the block that you would call a "latch in the previous frame" is functionally no different from a block elsewhere on the current frame?
The two differences are that it has been stored, and that full 2.5D movement has been unlocked.
> I don't see how it could have the same "address" but store a different value over time
You would implement this as one key frame of initial state fed into the decoder, followed by unlimited copies of a processing frame that does the calculation. The x-y position within a frame is your address, and each frame is a snapshot of time moving forwards.
I don't object to something external "feeding the same frame into the decoder" because so many early examples of things that were proved to be Turing complete required the operator to glue the input tape into a loop.
And maybe there is an existing codec or container out there that can build such a loop without anything external. (Like... DVDs allow you to loop, but I suspect the standard requires the loop target to be an I frame... Actual decoders might not) And you always have the option of just building a really long file (it will even zip really well)
Though as I said, I do hesitate to label something that can't terminate out of a loop as Turing complete. But you can just make it reach a steady state and have the operator recognise when it's finished.
if you can make a nand gate, you can make any other logic gate, thus turing complete
I think you also need some form of intermediate storage to be Turing complete.
Not that this example doesn't have intermediate storage... But I suspect you could create or discover a mechanism that is expressive enough to implement any chain of logic gates, but is incapable of expressing storage (can't even use the gates to implement a latch)
I'm also a little dubious of granting the "Truing complete" label to something that can't conditionally terminate (at minimum)
Maybe you can trick a video codec into looping forever without new key frames (in which case it can never terminate), but most likely this would need to be implemented unrolled, so always terminates after a fixed number of iterations.
It looks like you can only make "wires" that go down or to the right, so there's no way to connect up NANDs to make a latch or flip-flop (which would require wires going back up or to the left).
If you were limited to just a single frame of itra blocks, then yes. This would be an example of logic without storage.
Also quite limiting as wires could never cross.
But I was kinda jumping ahead and assuming VP8 allows you to mix and match intra and inter prediction modes within a single frame (and that inter prediction will feed into intra prediction... that might be a flawed assumption...)
Inter prediction should allow you to copy from any block on the previous frame, effetely creating unlimited length wires in any direction. This also makes the previous frame latched storage, without having to construct a latch from gates.
Exactly! Hopefully going to get around to it next weekend :)
Also, although you can't trivially cross wires, you can create a wire crossing using a few XOR gates [1]
[1] https://cs.stanford.edu/people/eroberts/courses/soco/project...
Yeah... I was worried that might be true.
> Inter prediction should allow you to copy from any block on the previous frame, effetely creating unlimited length wires in any direction.
I think "going inter" just gives you a third "dimension" along which you can still only travel one way -- but you need bidirectional travel (outputs feeding back into inputs) to implement memory. It makes sense to me that bidirectional travel is not possible here, since it would necessitate some kind of "keep processing until convergence" that could (and often would) prevent the decoder from making progress.
> This also makes the previous frame latched storage, without having to construct a latch from gates.
This makes me think we have different ideas of what "latched storage" means. I think the block that you would call a "latch in the previous frame" is functionally no different from a block elsewhere on the current frame? I don't see how it could have the same "address" but store a different value over time, which is what I'd call the defining property of all "storage".
> I think "going inter" just gives you a third "dimension" along which you can still only travel one way
Essentially intra prediction gives you two half dimensions. The temporal aspect of inter prediction gives you a third half dimension (which we could just call time). I agree that three half dimensions is not enough.
But... intra prediction also has motion compensation, which is essentially two full spacial dimensions that are accessible as long as you are traveling along the time dimension. And apparently 2.5D is enough. [1]
I'm not sure how you can should add these dimensions together, but arguably we are talking about 3.5D, which should be way more than enough.
> This makes me think we have different ideas of what "latched storage" means.
True. The value latched at the end of the previous frame would arguably count as globally-clocked storage, not latched. It's just in regular electronics, you are using latched storage to build clocked storage, so I kind of saw clocked as a superset of latched.
Which might be true, I can't really see a reason why you couldn't construct a latch from globally-clocked storage generally (as long as you have already solved the problem of moving backwards). At least in this case it's trivial, you just move both inputs back towards the top-left of the next frame.
> I think the block that you would call a "latch in the previous frame" is functionally no different from a block elsewhere on the current frame?
The two differences are that it has been stored, and that full 2.5D movement has been unlocked.
> I don't see how it could have the same "address" but store a different value over time
You would implement this as one key frame of initial state fed into the decoder, followed by unlimited copies of a processing frame that does the calculation. The x-y position within a frame is your address, and each frame is a snapshot of time moving forwards.
I don't object to something external "feeding the same frame into the decoder" because so many early examples of things that were proved to be Turing complete required the operator to glue the input tape into a loop.
And maybe there is an existing codec or container out there that can build such a loop without anything external. (Like... DVDs allow you to loop, but I suspect the standard requires the loop target to be an I frame... Actual decoders might not) And you always have the option of just building a really long file (it will even zip really well)
Though as I said, I do hesitate to label something that can't terminate out of a loop as Turing complete. But you can just make it reach a steady state and have the operator recognise when it's finished.
[1] https://cs.stanford.edu/people/eroberts/courses/soco/project...