5 ms·

I wonder if when these processors were developed, from a hardware standpoint, did the engineering team contemplate Turing completeness and the theory of computa

I wonder if when these processors were developed, from a hardware standpoint, did the engineering team contemplate Turing completeness and the theory of computation, or just try to satisfy a set of perceived customer needs.

stan_rogers 8y ago
If "tiring completeness" is supposed to read "Turing completeness", then including a conditional jump instruction of any sort completes the hardware requirement. The rest is about the number of conditions upon which that may be based and the access semantics, and that's where the CISC, RISC and hybrid approaches differ.
- aswanson 8y ago
  Agreed. I'm just wondering if they followed some theoretical schema or just responded to evolutionary forces. Most likely the latter.
  - deleted 8y ago
    [deleted]
  - xenadu02 8y ago
    It’s a direct evolution from 4004, 8008, 8080, to 8086. There was no compatibility but you can see the inspiration. IIRC 8086 was assembly compatible with 8080 but not binary compatible. At the time superscalar, register-renaming, vector-capable, and out-of-order were distant dreams and RAM was faster than the CPU. Everyone wrote assembly so the CPU designs accumulated instructions to make life easier on assembly programmers. 8086 was actually a stop-gap. The architecture astronauts at Intel that thought real hard about design were working on the iAPX 482, which was a stack machine that supported garbage collection in hardware(!)
    - dboreham 8y ago
      432
kccqzy 8y ago
It's difficult (though not quite impossible) to make a non-Turing-complete processor and still have it do useful things. So by making a processor that can do useful things, you have made it Turing complete.
burfog 8y ago
They got Turing completeness in just the MMU. This was surely unintended, just like Turing completeness in C++ template expansion and Turing completeness in sendmail configuration files. Here you go, computation via continuous MMU faults without actually completing any instructions: https://github.com/jbangert/trapcc https://github.com/jbangert/trapcc https://www.youtube.com/watch?v=eSRcvrVs5ug https://www.youtube.com/watch?v=eSRcvrVs5ug
- wolfgke 8y ago
  > They got Turing completeness in just the MMU. Since the amount of adressable memory on any CPU is finite, while a Turing machine needs in infinite band of memory, such claims of Turing-completeness of processors or in this case the MMU are clearly fraudulent. Only an abstract mathematical model can be Turing-complete - there exists no physical realization of a Turing-complete system/Turing machine and there will never be.
  - Sharlin 8y ago
    This is completely pointless pedantry. Everybody knows that, and nobody bothers to type "Turing-complete (up to memory constraints)" all the time. Real mathematicians do this all the time, taking shortcuts with the understanding that they could phrase it completely rigorously if it were necessary.
kryptiskt 8y ago
Turing completeness is easier to achieve than to avoid. If you have conditional branching and an unbounded store (memory is finite of course, but it's arbitrarily finite) it is Turing complete. So they may not have cared, but the analysis step would have been really simple. And if you don't want to bother with any formalia you can just implement Brainfuck (or less anachronistically you can go with FRACTAN), if it works you have something Turing complete.

stan_rogers 8y ago

If "tiring completeness" is supposed to read "Turing completeness", then including a conditional jump instruction of any sort completes the hardware requirement. The rest is about the number of conditions upon which that may be based and the access semantics, and that's where the CISC, RISC and hybrid approaches differ.

aswanson 8y ago
Agreed. I'm just wondering if they followed some theoretical schema or just responded to evolutionary forces. Most likely the latter.
- deleted 8y ago
  [deleted]
- xenadu02 8y ago
  It’s a direct evolution from 4004, 8008, 8080, to 8086. There was no compatibility but you can see the inspiration. IIRC 8086 was assembly compatible with 8080 but not binary compatible. At the time superscalar, register-renaming, vector-capable, and out-of-order were distant dreams and RAM was faster than the CPU. Everyone wrote assembly so the CPU designs accumulated instructions to make life easier on assembly programmers. 8086 was actually a stop-gap. The architecture astronauts at Intel that thought real hard about design were working on the iAPX 482, which was a stack machine that supported garbage collection in hardware(!)
  - dboreham 8y ago
    432

kccqzy 8y ago

It's difficult (though not quite impossible) to make a non-Turing-complete processor and still have it do useful things. So by making a processor that can do useful things, you have made it Turing complete.

burfog 8y ago

They got Turing completeness in just the MMU. This was surely unintended, just like Turing completeness in C++ template expansion and Turing completeness in sendmail configuration files. Here you go, computation via continuous MMU faults without actually completing any instructions: https://github.com/jbangert/trapcc https://github.com/jbangert/trapcc https://www.youtube.com/watch?v=eSRcvrVs5ug https://www.youtube.com/watch?v=eSRcvrVs5ug

wolfgke 8y ago
> They got Turing completeness in just the MMU. Since the amount of adressable memory on any CPU is finite, while a Turing machine needs in infinite band of memory, such claims of Turing-completeness of processors or in this case the MMU are clearly fraudulent. Only an abstract mathematical model can be Turing-complete - there exists no physical realization of a Turing-complete system/Turing machine and there will never be.
- Sharlin 8y ago
  This is completely pointless pedantry. Everybody knows that, and nobody bothers to type "Turing-complete (up to memory constraints)" all the time. Real mathematicians do this all the time, taking shortcuts with the understanding that they could phrase it completely rigorously if it were necessary.

kryptiskt 8y ago

Turing completeness is easier to achieve than to avoid. If you have conditional branching and an unbounded store (memory is finite of course, but it's arbitrarily finite) it is Turing complete. So they may not have cared, but the analysis step would have been really simple. And if you don't want to bother with any formalia you can just implement Brainfuck (or less anachronistically you can go with FRACTAN), if it works you have something Turing complete.