Reading up on TTA CPU designs and the wikipedia article states that

Some TTA implementations support conditional execution.

The trick to make an TTA ISA Turing-complete with an unconditional MOV instruction escapes me. Can anyone explain how that would work? (or share some resources where it is explained)

  • $\begingroup$ github.com/xoreaxeaxeax/movfuscator $\endgroup$ – sudhackar Feb 4 '18 at 9:19
  • $\begingroup$ Looks very cool, but I have trouble finding the answer in it... $\endgroup$ – obiwanjacobi Feb 4 '18 at 11:04
  • $\begingroup$ So, it cannot be done, or this niche topic is uninteresting? $\endgroup$ – obiwanjacobi Feb 21 '18 at 17:25
  • $\begingroup$ cl.cam.ac.uk/%7Esd601/papers/mov.pdf is the paper that says mov is turing complete. Check out the repo I linked and the additional documents. $\endgroup$ – sudhackar Feb 22 '18 at 15:41
  • $\begingroup$ So you use the values as an indirect memory addressing index and the set (mov) known but different values into them. That is so lame and corrupts your memory. $\endgroup$ – obiwanjacobi Feb 23 '18 at 7:11

For a CPU designed to use a TTA (Transport Triggered Architecture), one way to implement conditional branch could use a couple of addresses for these purposes:

  • BRANCH_ADDRESS: stores the location to branch to
  • BRANCH_ZERO: Sets PC to BRANCH_ADDRESS when value written is 0. Otherwise does nothing.

This could be used to implement a 'branch-if-zero'. You could also add additional addresses that implement other branch modes, including those ithat hook into flags/state of other components hooked up to the TTA CPU, such as an ALU.


It all comes down to what you consider "conditional". For example, when you trigger an AND, the output varies depending on its operands: is that a conditional operation?

In this case, Wikipedia is talking about "conditional transport" (the ability to turn busses on and off via a register), not "conditional execution" (the ability to jump to different places based on some condition). The latter is what's needed for Turing-completeness, as you correctly pointed out.

In some TTAs, you can directly write to the program counter; in others, there's a functional unit that handles instruction fetching and decoding and all that, and it has ports for jumps. In the latter case, conditional jumps can be implemented with multiple ports, just like you might expect: write an address to the "jump destination" port, then write a value to the "branch if zero trigger" port, and it'll branch to the destination if the trigger value was zero.

Wikipedia suggests that a single port can be used for this:

TTA implementations that only support unconditional data transports, such as the MAXQ, typically have a special function unit tightly connected to the program counter that responds to a variety of destination addresses. Each such address, when used as the destination of a "move", has a different effect on the program counter—each "relative branch " instruction has a different destination address for each condition; and other destination addresses are used CALL, RETNZ, etc.

This has the same effect: you just have to write the destination and the "opcode" to the same port, one after the other.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.