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
JNZ  address    ; if (r0 != 0) then jump to <address>. Else, skip.
LDR ri, address  ; load value at <address> into ri
STR ri, address  ; store the value in <ri> to <address>

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.
  • 1
    $\begingroup$ 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 $\endgroup$ – Marzio De Biasi Feb 14 '14 at 18:38
  • 2
    $\begingroup$ @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. $\endgroup$ – user17100 Feb 14 '14 at 18:46
  • $\begingroup$ believe there are some proofs that mere/fairly simple "counter machines" are Turing complete.... $\endgroup$ – vzn Feb 14 '14 at 21:10
  • $\begingroup$ @vzn Even with the limit of 16 instructions? $\endgroup$ – felix Feb 14 '14 at 22:22
  • $\begingroup$ @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". $\endgroup$ – Marzio De Biasi Feb 14 '14 at 23:27

even many simple counter machines have been proven Turing complete and this result might be surprising to nonresearchers (or researchers who dont specialize in the area). suggest a more relevant research question would be to review the existing models (many listed on wikipedia), determine if yours fits into them anywhere, and if it does not, describe the precise difference with one of the "nearest" models analyzed in the literature.

  • 2
    $\begingroup$ The point is that the code can have no more than 16 instructions so it can't possibly be Turing complete. There are more than a finite number of possible programs :) $\endgroup$ – felix Feb 15 '14 at 14:06
  • $\begingroup$ oh! ok! oops! (typo? do you mean there are no more than a finite # of programs?) missed that on skimming/ thought he meant 16 instructions in the instruction set. the other question about limited address space seems trivial also & the whole things behavior is likely equivalent to an FSM... might work on a proof of that but it might get downvoted around here also =( ... exercise for reader? ... anyway the question did not seem research level without more bkg connection to literature etc $\endgroup$ – vzn Feb 15 '14 at 14:55
  • $\begingroup$ Yes I meant no more than a finite # of programs. $\endgroup$ – felix Feb 15 '14 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.