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