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

**URL:** <https://discourse.julialang.org/t/assembly-is-jump-if-not-zero-more-expressive-than-jump-if-odd/81391>\
**Category:** Offtopic\
**Tags:** question\
**Created:** [May 20, 2022, 5:51pm UTC](https://discourse.julialang.org/t/assembly-is-jump-if-not-zero-more-expressive-than-jump-if-odd/81391 "2022-05-20T17:51:18Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![mbaz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbaz/32/17295_2.png) [@mbaz](https://discourse.julialang.org/u/mbaz)\
**Post date:** [May 20, 2022, 5:51pm UTC](https://discourse.julialang.org/t/assembly-is-jump-if-not-zero-more-expressive-than-jump-if-odd/81391/1 "2022-05-20T17:51:18Z")

</div>

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:

> [@On the arbitrariness of truth(iness)](https://discourse.julialang.org/t/on-the-arbitrariness-of-truth-iness/81381/1):
>
> But we could just as easily have had `je` and `jo` (jump if even, jump if odd) as assembly instructions that jump based only on the last bit of a register.

I teach an introductory programming course, and one of the concepts I introduce first is the [“paper computer”](https://en.wikipedia.org/wiki/WDR_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`.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [May 20, 2022, 5:57pm UTC](https://discourse.julialang.org/t/assembly-is-jump-if-not-zero-more-expressive-than-jump-if-odd/81391/2 "2022-05-20T17:57:07Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![mbaz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbaz/32/17295_2.png) [@mbaz](https://discourse.julialang.org/u/mbaz)\
**Post date:** [May 20, 2022, 6:00pm UTC](https://discourse.julialang.org/t/assembly-is-jump-if-not-zero-more-expressive-than-jump-if-odd/81391/3 "2022-05-20T18:00:14Z")

</div>

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)](https://en.wikipedia.org/wiki/One-instruction_set_computer) 😅

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

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [May 20, 2022, 7:17pm UTC](https://discourse.julialang.org/t/assembly-is-jump-if-not-zero-more-expressive-than-jump-if-odd/81391/4 "2022-05-20T19:17:34Z")

</div>

A post was merged into an existing topic: [On the arbitrariness of truth(iness)](https://discourse.julialang.org/t/on-the-arbitrariness-of-truth-iness/81381/15)

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [May 20, 2022, 7:16pm UTC](https://discourse.julialang.org/t/assembly-is-jump-if-not-zero-more-expressive-than-jump-if-odd/81391/5 "2022-05-20T19:16:50Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [May 20, 2022, 7:19pm UTC](https://discourse.julialang.org/t/assembly-is-jump-if-not-zero-more-expressive-than-jump-if-odd/81391/6 "2022-05-20T19:19:36Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![mbaz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbaz/32/17295_2.png) [@mbaz](https://discourse.julialang.org/u/mbaz)\
**Post date:** [May 20, 2022, 7:22pm UTC](https://discourse.julialang.org/t/assembly-is-jump-if-not-zero-more-expressive-than-jump-if-odd/81391/7 "2022-05-20T19:22:47Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![lawless-m](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lawless-m/32/30869_2.png) [@lawless-m](https://discourse.julialang.org/u/lawless-m)\
**Post date:** [May 20, 2022, 7:29pm UTC](https://discourse.julialang.org/t/assembly-is-jump-if-not-zero-more-expressive-than-jump-if-odd/81391/9 "2022-05-20T19:29:20Z")

</div>

My edit got caught in the split

Bell Labs produced the CARDIAC computer:

“CARDboard Illustrative Aid to Computation”

> **[CARDboard Illustrative Aid to Computation](https://en.wikipedia.org/wiki/CARDboard_Illustrative_Aid_to_Computation)**
>
> CARDIAC (CARDboard Illustrative Aid to Computation) is a learning aid developed by David Hagelbarger and Saul Fingerman for Bell Telephone Laboratories in 1968 to teach high school students how computers work. The kit consists of an instruction manual and a die-cut cardboard "computer".
> The computer "operates" by means of pencil and sliding cards. Any arithmetic is done in the head of the person operating the computer. The computer operates in base 10 and has 100 memory cells which can hold sig...

[![](https://global.discourse-cdn.com/julialang/original/3X/a/e/ae7fca3f894aad8f5f5ed8768d48b37254d28880.jpeg "Quick Tour of the Built CARDIAC computer") ](https://www.youtube.com/watch?v=CW96m7R0u-s)

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [May 20, 2022, 7:31pm UTC](https://discourse.julialang.org/t/assembly-is-jump-if-not-zero-more-expressive-than-jump-if-odd/81391/10 "2022-05-20T19:31:10Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![mbaz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbaz/32/17295_2.png) [@mbaz](https://discourse.julialang.org/u/mbaz)\
**Post date:** [May 20, 2022, 7:41pm UTC](https://discourse.julialang.org/t/assembly-is-jump-if-not-zero-more-expressive-than-jump-if-odd/81391/11 "2022-05-20T19:41:40Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![mnemnion](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mnemnion/32/206596_2.png) [@mnemnion](https://discourse.julialang.org/u/mnemnion)\
**Post date:** [April 9, 2024, 5:57pm UTC](https://discourse.julialang.org/t/assembly-is-jump-if-not-zero-more-expressive-than-jump-if-odd/81391/12 "2024-04-09T17:57:58Z")

</div>

> [@mbaz](#):
>
> 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.

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.