# Assembly: is "jump if not zero" more expressive than "jump if odd"?

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

3 Likes

This isa is already significantly over-complicated. `ADD` and `JMP` are redundant.

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.

1 Like

A post was merged into an existing topic: On the arbitrariness of truth(iness)

I split this into a new topic because it’s very interesting but I think it’s a bit in the weeds for the original thread.

1 Like

How does this computer input or output anything? Are registers considered inputs/outputs?

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.

My edit got caught in the split

Bell Labs produced the CARDIAC computer:

“CARDboard Illustrative Aid to Computation”

3 Likes

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.

1 Like

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.

2 Likes