5 ms·

x86 is Turing-complete with no registers

89 points by walrus 13y ago

rtpg 13y ago
Another good example of a Turing tarpit My favorite is the OISC(One instruction set computer) http://esolangs.org/wiki/OISC http://esolangs.org/wiki/OISC (Esolang is probably the best timewaster for language nerds)
- arethuza 13y ago
  Or for the functionally inclined - S & K combinators: http://en.wikipedia.org/wiki/SKI_combinator_calculus http://en.wikipedia.org/wiki/SKI_combinator_calculus I just found this document which describes a Q combinator that can be used to define S & K: http://www.cs.uu.nl/research/techreps/repo/CS-1989/1989-14.pdf http://www.cs.uu.nl/research/techreps/repo/CS-1989/1989-14.p...
  - sp332 13y ago
    I'm not sure I understand the definition of Q from that paper. Q = \xyz.x right? But that requires assuming lambda calculus, which is small I guess but not what I would call minimal.
    - arethuza 13y ago
      I must admit that I just skimmed that paper - I did see that and thought it looked a bit odd but assumed it was just me!
    - walrus 13y ago
      You can express it formally in terms of a rewrite rule: If Δ is a derivation ending in an expression of the form α(((Qβ)γ)δ)ι, then Δ followed by the term αβι is a derivation. Writing it as \xyz.x is just a less noisy way of saying that.
unwind 13y ago
This was cool, almost as much as for showing weird magic you can do with Linux' ptrace() as for the actual thing done. Also, you know you're reading the page of a True Language ... Person when you get gems like: Brainfuck isn't the simplest language out there (try Subleq) but it's pretty familiar as an imperative, structured-control language. So I think compiling from Brainfuck makes this feel "more real" than compiling from something super weird. Not sure how many people consider Brainfuck "pretty familiar" (especially at this level) or "real", even with quotes. :)
- arethuza 13y ago
  Numbers? Memory addresses? Subleq is rather baroque compared to the ascetic world of combinators... ;-) NB: As a final year project on my CS course in the 80s I did benchmarking on the efficiency of different sets of combinators for executing a toy functional programming language - the simplest set of combinators I used was SK and that was quite impressively awful to do something like multiplication. Quite interested to see how bad a single combinator scheme would be....
  - sp332 13y ago
    Here's the simplest one I can find, the Binary Lambda Calculus: BLC Syntax <term> ::= 00 | 01 | 1 <term> <term> BLC Semantics (as string-rewriting rules for any terms x, y, z) 1100xy --> x 11101xyz --> 11xz1yz http://homepages.cwi.nl/~tromp/cl/cl.html http://homepages.cwi.nl/~tromp/cl/cl.html
- reeses 13y ago
  It's a bit tongue-in-cheek. Much of the narrative is, with cute tidbits such as Code that self-modifies by calling read() is clearly the future of computing.
- squidfood 13y ago
  Once you get started with a Brainfuck problem, it's amazing how quickly you forget that it's supposed to be "unusable" and dive into the algorithms like any other language.
fogleman 13y ago
I thought MOV alone was turing complete.
- kd0amg 13y ago
  MOV is only Turing-complete if you also add in a looping mechanism (which is to say, MOV alone is not Turing-complete). This uses unconditional jumps to "constant" addresses (as opposed to conditional branches or jumps to the address held in some register) and dynamically overwrites their target addresses, so that includes its own looping mechanism.
  - adrianN 13y ago
    Page fault handling in itself is Turing complete. No instructions needed. > https://www.usenix.org/conference/woot13/workshop-program/presentation/bangert https://www.usenix.org/conference/woot13/workshop-program/pr...
- reeses 13y ago
  Addressed (hah) in the article. It's Turing complete for naive values of Turing complete.
deleted 13y ago
[deleted]
lifthrasiir 13y ago
> These systems are Turing-complete when you add an external tape using I/O, but so is a finite-state machine! There is a related concept called Bounded-Storage Machine for memory-bounded TM-like abstractions. This computation model is very common with esoteric programming languages. http://esolangs.org/wiki/Bounded-storage_machine http://esolangs.org/wiki/Bounded-storage_machine
stephencanon 13y ago
Forget registers; modern x86 is turing-complete without any instructions: https://github.com/jbangert/trapcc https://github.com/jbangert/trapcc
snake_plissken 13y ago
I still have difficulty understanding exactly what a Turing machine is.
- pash 13y ago
  I suggest reading Turing's paper in the form of Charles Petzold's book The Annotated Turing [0]. 0. http://www.amazon.com/gp/aw/d/0470229055 http://www.amazon.com/gp/aw/d/0470229055
  - SixSigma 13y ago
    Fantastic book, I thought Turing machines were just some abstract concept just exploring computer science until Petzold opened my eyes.
    - ramses0 13y ago
      You'll love this video then if you haven't already seen it: http://www.youtube.com/watch?v=E3keLeMwfHY http://www.youtube.com/watch?v=E3keLeMwfHY
tptacek 13y ago
Similar vein: https://news.ycombinator.com/item?id=5261598 https://news.ycombinator.com/item?id=5261598
StephenFalken 13y ago
On the other extreme, there was the Unlimited Register Machine (URM) [1] specified on Nigel J. Cutland's book: Computability, An introduction to recursive function theory. [1] http://faculty.oxy.edu/rnaimi/home/URMsim.htm http://faculty.oxy.edu/rnaimi/home/URMsim.htm
bnegreve 13y ago
> But x86 itself also has a limit on addressable memory. So does C, because sizeof(void *) is finite. These systems are Turing-complete when you add an external tape using I/O, but so is a finite-state machine! You could argue that I/O operations (which can emulate an unbounded tape) are defined in the C standard library, which is of course not the case of finite state machines. So in absence of instantiation bounds C together with the C standard library IS Turing complete.

89 points by walrus 13y ago

rtpg 13y ago

Another good example of a Turing tarpit My favorite is the OISC(One instruction set computer) http://esolangs.org/wiki/OISC http://esolangs.org/wiki/OISC (Esolang is probably the best timewaster for language nerds)

arethuza 13y ago
Or for the functionally inclined - S & K combinators: http://en.wikipedia.org/wiki/SKI_combinator_calculus http://en.wikipedia.org/wiki/SKI_combinator_calculus I just found this document which describes a Q combinator that can be used to define S & K: http://www.cs.uu.nl/research/techreps/repo/CS-1989/1989-14.pdf http://www.cs.uu.nl/research/techreps/repo/CS-1989/1989-14.p...
- sp332 13y ago
  I'm not sure I understand the definition of Q from that paper. Q = \xyz.x right? But that requires assuming lambda calculus, which is small I guess but not what I would call minimal.
  - arethuza 13y ago
    I must admit that I just skimmed that paper - I did see that and thought it looked a bit odd but assumed it was just me!
  - walrus 13y ago
    You can express it formally in terms of a rewrite rule: If Δ is a derivation ending in an expression of the form α(((Qβ)γ)δ)ι, then Δ followed by the term αβι is a derivation. Writing it as \xyz.x is just a less noisy way of saying that.

unwind 13y ago

This was cool, almost as much as for showing weird magic you can do with Linux' ptrace() as for the actual thing done. Also, you know you're reading the page of a True Language ... Person when you get gems like: Brainfuck isn't the simplest language out there (try Subleq) but it's pretty familiar as an imperative, structured-control language. So I think compiling from Brainfuck makes this feel "more real" than compiling from something super weird. Not sure how many people consider Brainfuck "pretty familiar" (especially at this level) or "real", even with quotes. :)

arethuza 13y ago
Numbers? Memory addresses? Subleq is rather baroque compared to the ascetic world of combinators... ;-) NB: As a final year project on my CS course in the 80s I did benchmarking on the efficiency of different sets of combinators for executing a toy functional programming language - the simplest set of combinators I used was SK and that was quite impressively awful to do something like multiplication. Quite interested to see how bad a single combinator scheme would be....
- sp332 13y ago
  Here's the simplest one I can find, the Binary Lambda Calculus: BLC Syntax <term> ::= 00 | 01 | 1 <term> <term> BLC Semantics (as string-rewriting rules for any terms x, y, z) 1100xy --> x 11101xyz --> 11xz1yz http://homepages.cwi.nl/~tromp/cl/cl.html http://homepages.cwi.nl/~tromp/cl/cl.html
reeses 13y ago
It's a bit tongue-in-cheek. Much of the narrative is, with cute tidbits such as Code that self-modifies by calling read() is clearly the future of computing.
squidfood 13y ago
Once you get started with a Brainfuck problem, it's amazing how quickly you forget that it's supposed to be "unusable" and dive into the algorithms like any other language.

fogleman 13y ago

I thought MOV alone was turing complete.

kd0amg 13y ago
MOV is only Turing-complete if you also add in a looping mechanism (which is to say, MOV alone is not Turing-complete). This uses unconditional jumps to "constant" addresses (as opposed to conditional branches or jumps to the address held in some register) and dynamically overwrites their target addresses, so that includes its own looping mechanism.
- adrianN 13y ago
  Page fault handling in itself is Turing complete. No instructions needed. > https://www.usenix.org/conference/woot13/workshop-program/presentation/bangert https://www.usenix.org/conference/woot13/workshop-program/pr...
reeses 13y ago
Addressed (hah) in the article. It's Turing complete for naive values of Turing complete.

deleted 13y ago

[deleted]

lifthrasiir 13y ago

> These systems are Turing-complete when you add an external tape using I/O, but so is a finite-state machine! There is a related concept called Bounded-Storage Machine for memory-bounded TM-like abstractions. This computation model is very common with esoteric programming languages. http://esolangs.org/wiki/Bounded-storage_machine http://esolangs.org/wiki/Bounded-storage_machine

stephencanon 13y ago

Forget registers; modern x86 is turing-complete without any instructions: https://github.com/jbangert/trapcc https://github.com/jbangert/trapcc

snake_plissken 13y ago

I still have difficulty understanding exactly what a Turing machine is.

pash 13y ago
I suggest reading Turing's paper in the form of Charles Petzold's book The Annotated Turing [0]. 0. http://www.amazon.com/gp/aw/d/0470229055 http://www.amazon.com/gp/aw/d/0470229055
- SixSigma 13y ago
  Fantastic book, I thought Turing machines were just some abstract concept just exploring computer science until Petzold opened my eyes.
  - ramses0 13y ago
    You'll love this video then if you haven't already seen it: http://www.youtube.com/watch?v=E3keLeMwfHY http://www.youtube.com/watch?v=E3keLeMwfHY

tptacek 13y ago

Similar vein: https://news.ycombinator.com/item?id=5261598 https://news.ycombinator.com/item?id=5261598

StephenFalken 13y ago

On the other extreme, there was the Unlimited Register Machine (URM) [1] specified on Nigel J. Cutland's book: Computability, An introduction to recursive function theory. [1] http://faculty.oxy.edu/rnaimi/home/URMsim.htm http://faculty.oxy.edu/rnaimi/home/URMsim.htm

bnegreve 13y ago

> But x86 itself also has a limit on addressable memory. So does C, because sizeof(void *) is finite. These systems are Turing-complete when you add an external tape using I/O, but so is a finite-state machine! You could argue that I/O operations (which can emulate an unbounded tape) are defined in the C standard library, which is of course not the case of finite state machines. So in absence of instantiation bounds C together with the C standard library IS Turing complete.