x86 is Turing-complete with no registers | Hacker News Reader

x86 is Turing-complete with no registers

mainisusuallyafunction.blogspot.com

89 pointswalrus23 comments

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. :)

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....

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

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.

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.

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

Another good example of a Turing tarpit

My favorite is the OISC(One instruction set computer) http://esolangs.org/wiki/OISC

(Esolang is probably the best timewaster for language nerds)

Or for the functionally inclined - S & K combinators:

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.p...

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.

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!

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.

> 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

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

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

Fantastic book, I thought Turing machines were just some abstract concept just exploring computer science until Petzold opened my eyes.

You'll love this video then if you haven't already seen it: http://www.youtube.com/watch?v=E3keLeMwfHY

> 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.

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

I thought MOV alone was turing complete.

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.

Page fault handling in itself is Turing complete. No instructions needed.

> https://www.usenix.org/conference/woot13/workshop-program/pr...

Addressed (hah) in the article. It's Turing complete for naive values of Turing complete.

Reply on news.ycombinator.com