# Interesting programs on small machines

I am teaching a course and have a tiny implementation of a counter-style machine that has the following instructions and two registers, r0 & r1

INC ri   ; ri <- ri + 1
DEC ri  ; ri <- r1 - 1


What interesting programs can I make using this instruction set using no more than 16 instructions (the range of my address space).

So far, the best I have is "check if memory contains an odd value in the range 0-7"

Also, does it help if I add the following instruction:

JLT address ; if (r0 < 0) then jump to <address>. Else, skip.

• STR ri, address should be "store the value in <ri> to <address>". And you should also specify where the input is given (if any), and what is the halt condition (and the result of the computation e.g. YES/NO/value in register?). However I think it is not a research-level question (see cstheory FAQ), so a better place for question like this is (the nice) codegolf.stackexchange.com – Marzio De Biasi Feb 14 '14 at 18:38
• @MarzioDeBiasi I don't agree or more accurately I do think there is potentially a nice theory+teaching question here which is on topic. It isn't immediately obvious what is or is not computable at least to me and it seems the sort of mix of practice and theory some students would find very enlightening. – user17100 Feb 14 '14 at 18:46
• believe there are some proofs that mere/fairly simple "counter machines" are Turing complete.... – vzn Feb 14 '14 at 21:10
• @vzn Even with the limit of 16 instructions? – felix Feb 14 '14 at 22:22
• @Erhart: to be honest, I myself don't agree with myself :-) :-) ! ... I like the question though it misses the input/output specifications (for example: input value(s) is (are) placed in address 15,14,..., the output shoud be placed in address 15) and - in my opinion - JNZ and DEC should be replaced with a single DJZ (decrement and test if zero) and JMP (unconditional jump). And it is a very nice challenge for the students ... but I still have some doubts on it's "research-levelness". – Marzio De Biasi Feb 14 '14 at 23:27