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

Offtopic
#1

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
On the arbitrariness of truth(iness)
#2

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

#3

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

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
#4

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

#5

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
#6

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

#7

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.

#9

My edit got caught in the split

Bell Labs produced the CARDIAC computer:

“CARDboard Illustrative Aid to Computation”

3 Likes
#10

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
#11

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