4 ms·
I'm in the process of writing a tutorial on this/hardware synthesis from first principles, but general purpose computers are way less magical when you think of
by lpage 10y ago
I'm in the process of writing a tutorial on this/hardware synthesis from first principles, but general purpose computers are way less magical when you think of components such the ALU as a mapping of binary inputs to binary outputs: a truth table. From there you can explicitly enumerate all possible inputs and outputs (for small word sizes at least) and go directly from said truth table to (inefficient) hardware.
Related: mov is Turing-complete [1] and X86 MMU fault handling is Turing-complete [2]
edit: formatting
[1] https://www.cl.cam.ac.uk/~sd601/papers/mov.pdf https://www.cl.cam.ac.uk/~sd601/papers/mov.pdf
[2] https://news.ycombinator.com/item?id=5261598 https://news.ycombinator.com/item?id=5261598
- waynecolvin 10y agoI suspect it would be difficult (impossible?) without relative position addressing modes and/or other tricks. A conventional stack would need some way to access an offset away from the base, but perhaps you could use self-modifying code. Perhaps relative from current position like brainfk. All general computation needs either a direct or convoluted means of achieving conditions too. A tricky formula exploiting abs(x) could be used to produce {0, 1} but...
- lpage 10y agoRight, my comment retarding truth tables was only in reference to combinatorial logic. That said, pure circuit models of computations exist, and are interesting from a theoretical standpoint at least. They don't translate to hardware, though. As you noted doing arbitrary computation with (finite) circuits requires some type of feedback/sequential logic.
- foota 10y agoAn amusing application of mov's turing completeness https://github.com/xoreaxeaxeax/movfuscator https://github.com/xoreaxeaxeax/movfuscator