<p>even many simple <a href="http://en.wikipedia.org/wiki/Counter_machine" rel="nofollow">counter machines</a> 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 <em>research</em> 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.</p>

CC BY-SA 3.0
2014-02-15T14:06:28.257Z
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 :)
Simd
CC BY-SA 3.0
2014-02-15T14:55:09.813Z
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
vzn
CC BY-SA 3.0
2014-02-15T15:17:53.863Z
Yes I meant no more than a finite # of programs.
Simd
CC BY-SA 3.0
2014-02-15T03:57:26.617Z
2014-02-15T03:57:26.617Z
vzn
<p>I am teaching a course and have a tiny implementation of a counter-style machine that has the following instructions and two registers, r0 &amp; r1</p>

<pre><code>INC ri   ; ri &lt;- ri + 1
DEC ri  ; ri &lt;- r1 - 1
JNZ  address    ; if (r0 != 0) then jump to &lt;address&gt;. Else, skip.
LDR ri, address  ; load value at &lt;address&gt; into ri
STR ri, address  ; store the value in &lt;ri&gt; to &lt;address&gt;
</code></pre>

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

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

<p>Also, does it help if I add the following instruction:</p>

<pre><code>JLT address ; if (r0 &lt; 0) then jump to &lt;address&gt;. Else, skip.
</code></pre>

CC BY-SA 3.0
2014-02-14T18:38:16.407Z
*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](http://cstheory.stackexchange.com/tour)), so a better place for question like this is (the nice) http://codegolf.stackexchange.com
Marzio De Biasi
CC BY-SA 3.0
2014-02-14T21:10:39.073Z
believe there are some proofs that mere/fairly simple "counter machines" are Turing complete....
vzn
CC BY-SA 3.0
2014-02-14T22:22:17.850Z
@vzn Even with the limit of 16 instructions?
Simd
CC BY-SA 3.0
2014-02-14T23:27:02.203Z
@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
<soft-question><teaching>
Interesting programs on small machines
HarryH
# Interesting programs on small machines

(Asked by: username_0 on 2014-02-14)

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 . Else, skip.
LDR ri, address  ; load value at  into ri
STR ri, address  ; store the value in  to 

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 . Else, skip.

**Tags:** soft-question, teaching

> **Comments:**
> **username_1**: *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](http://cstheory.stackexchange.com/tour)), so a better place for question like this is (the nice) http://codegolf.stackexchange.com  
> **username_2**: believe there are some proofs that mere/fairly simple "counter machines" are Turing complete....  
> **username_3**: @username_2 Even with the limit of 16 instructions?  
> **username_1**: @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".  

---

## 1 answers

### Answer by username_2 on 2014-02-15. Score: -4

even many simple [counter machines](http://en.wikipedia.org/wiki/Counter_machine) 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.

> **Comments:**
> **username_3**: 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 :)  
> **username_2**: 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  
> **username_3**: Yes I meant no more than a finite # of programs.  

---

