I’m completely in favor of disallowing truthy and falsey values, and I hope the core team is never swayed otherwise. Having said that, this claim caught my eye:
I teach an introductory programming course, and one of the concepts I introduce first is the “paper computer”. This is a computer that only exists on paper and runs by the user keeping track of its state using a pencil. My version has 16 words of code memory, 7 general purpose registers (R0 to R6), a program counter (PC) and five instructions:
STP: stops execution
SKP R#: R# == 0 ? PC <- PC+2 : PC <- PC+1
JMP ##: PC <- ##
ADD R#: R# <- R#+1, PC <- PC+1
SUB R#: R# <- R#-1, PC <- PC+1
This instruction set is Turing complete, so it allows me to define “computational thinking” as “make this machine solve your problem for you”. Anyway, the first exercise is to write a program to add R0 to R1 and store the result in R2.
I’m wondering, can this problem be solved if the meaning of SKP R# is changed to “skip if even”? After a few minutes of thought, I’m leaning towards “no”, but I’d like to be proven wrong. If it can’t be done, it’d mean that there’s something fundamental in jz and jnz that is not shared by je and jo.
Indeed, but I felt I needed to make this little concession to ergonomics/user convenience… in my defense, I do mention the one-instruction computer(s)
EDIT: BTW, if you remove ADD and JMP but keep “skip if even”, then I claim the problem still can’t be solved. The problem is lack of cmparison to zero (or alternatively to any convenient fixed constant). One-instruction computers all require (some kind of) comparison with zero.
Yes. The registers and instruction memory are given initial values, PC is set to zero, and then computation starts and runs until STP is reached. Results are written to registers as well.
I think you’re right that it’s not as expressive. I was thinking that you’d have comparison instructions that would compare values and leave 0/1 values in a register, which you’d then check. But this simple ISA doesn’t waste those extra instructions. I can’t see a way to implement the simple add one register to another program given as an example on that wikipedia page. You need some way to compare a value to a threshold, which the parity check doesn’t give.
I don’t see how to implement it either; I wish I knew how to prove it’s impossible, though.
What is most interesting is it’d seem that “ability to compare against a fixed, known threshold” is a requirement for Turing completeness. I’ve never seen this stated so explicitly, but I think it’s stated implicitly in the definition of a Turing machine.
Given this, zero is probably the most natural threshold. Things should still work with other thresholds, though.
Turing completeness means that the system can compute anything computable, so this does require “ability to compare against a fixed, known threshold”. But it also requires “ability to conditionally branch on even and odd”. I think a better word than ‘requires’ is ‘implies’ here.
The lambda calculus, which is Turing complete, doesn’t even have numbers, so no comparison of numbers, threshold-based or otherwise, is a primitive of the system.
Of course this comparison can be build with the lambda calculus, but so can the Mandelbrot set.
So, no, “compare against zero” isn’t a necessary primitive operation for Turing completeness, it’s sufficient to be able to build it.
I think there’s a variation on this question which is interesting, but it turns out to be difficult to formulate precisely. You’d need to define what the class of automata you’re interested is and isn’t allowed to do. It’s probably true that taking your paper computer and swapping SKP for a parity test won’t work, although that’s a conjecture at this point. But that doesn’t generalize, and as the counterexample of lambda calculus shows, the proposition isn’t true in complete generality, unless it’s treated as a trivial result: namely that Turing complete machines can by definition compute, and a function returning true if the argument is zero is of course computable.
That clearly isn’t what you meant, and I think there’s a kernel of an interesting question there! We’d need to figure out what it is, and that might start with a proof of the conjecture that “parity SKP paper computer” isn’t Turing complete.
