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.