Talk:Subleq
I've added some programs to my Subleq OISC webpage, for anyone interested. Included is this quine (not elegant, but it works!):
[67,67,3,68,68,6,65,68,9,67,66,12,36,36,15,66,36,18, 64,36,21,63,36,27,66,66,-1,36,36,30,66,36,33,66,66, 36,36,66,39,36,36,42,68,36,45,52,52,48,36,52,51,66, 120,54,63,67,57,63,68,60,66,66,9,-1,69,-69,0,67,137]
--r.e.s. (Talk) 18:25, 26 December 2007 (UTC)
Renaming/moving article content?
The content of this article is written as though OISCs must use Subleq according to one person's (Mazonka's?) extensions to the concept. But Subleq OISCs have been called by that name for many years, and the term would seem to refer to any OISC that uses Subleq ("Subtract and Branch if Less-than-or-Equal" to zero) as its only instruction — and there are even variants of how Subleq works, aside from from various useful "extensions" like i/o. So, I suggest that either the present extensive version-specific content be moved to an article more appropriately named, or that it be edited to identify the version-specific content, allowing equal status for other versions of Subleq OISC. I'd like some feedback before I do either of these. --r.e.s. (Talk) 22:17, 31 December 2007 (UTC)
As I commented above two years ago, subleq is the name of a type of OISC, as described at this Wikipedia page. The name should not be appropriated for someone's special version of it together with their special-version assembler. The article should be edited to reflect this. --r.e.s. (Talk) 15:20, 7 September 2009 (UTC)
Computational Class
It appears that the dialect of subleq described here is Turing complete only if the value of each memory location is unbounded. This would allow an unbounded code space (the convention that a previously undefined memory location be initialized to 0 seems natural) which would fulfill the Turing Completeness criterion of arbitrarily large memory (since data shares the same space with code). However, even a bounded code space with unbounded memory values would almost assuredly be enough for TC, as one could construct a Minsky machine.
On the other hand, bounded memory values in an unbounded code space - a la many brainfuck dialects - would not be sufficient, because only a finite portion of the code space is accessible.
A logical follow-on question is this: What about relative rather than absolute branching? Using this variation on subleq an unbounded code space would be accessible even with bounded memory values, and should be Turing Complete.
So, I propose the following information be added to the main page: "Absolute addressing dialects of Subleq are Turing Complete only if the memory values are unbounded. Relative addressing dialects of Subleq are Turing Complete even with bounded memory values." --Nthern 18:22, 15 September 2008 (UTC)
- I am not convinced that this is sufficient, since the branch distance would still be bounded, and so the more significant bits of your program counter would behave similarly to a single integer that can only be incremented and decremented, which seems like a serious limit on how you can branch. I don't recall that this is enough for TC. It is of course complicated by the fact that the code could vary arbitrarily dependent on this program counter, but my immediate intuition is that this is not enough. --Ørjan 14:15, 16 September 2008 (UTC)
- Wait, of course it should be enough, since you can simulate a universal turing machine with this layout. --Ørjan 14:28, 16 September 2008 (UTC)
- This is trivially true of all computing hardware and software. McChuck (talk) 18:52, 21 October 2022 (UTC)
R.E.S.
Hey r.e.s., where'd your web page go? I went there a couple of times, but hadn't yet downloaded your python Subleq interpreters. Now I'm wishing I had. I also liked the info you had on the different mark i vs. mark ii and absolute vs. relative dialects. Hope you show up again soon. --Nthern 17:42, 2 October 2008 (UTC)
- Sorry -- I've been away for a long while and only just noticed your message here; thanks for the kind words. Unfortunately, I've lost most of the content of my personal website, including the Subleq pages and the pages on BCT. Needless to say, I would appreciate hearing from anyone who has copies of any of those pages. (r.e.s.0001 [at] gmail.com) --r.e.s. (Talk) 05:14, 12 February 2009 (UTC)
A shorter HelloWorld program in a loop, length 35
# print the p(initial data) p:data -1 ?+1 # increment p T p ?+1 Z p ?+1 # check if p >= E then halt E p -1 E p ?+1 Z Z p # our "Hello, world!\n" data data:72 101 108 108 111 44 32 119 111 114 108 100 33 10 E:E # constant -1 and 0 T:-1 Z:0
Of course, You can change the data between "data:" and "E:E" in ASCII.
Without the assembler syntax, it looks like
18 -1 3 33 0 6 34 0 9 32 0 -1 32 0 15 34 34 0 72 101 108 108 111 44 32 119 111 114 108 100 33 10 32 -1 0
NOTE: This can not run on subleq.py :( but can run on my own subleq emulator and assembler :) I can't visit mazonka.com so I wrote it myself XD
- Maybe it's me, but I'm not making much sense of your code. At position 3, you increment p. So far so good. At 6, you subtract 0 from p, but go to the next instruction if 0. Isn't that a NOP? At 9, you subtract E from what's at 0 then set C to -1 if it's le to zero. It's always going to be less than 0 so the program will end. When run in my interpreter, It outputs and H and exits. Exactly what I expect it to do after reading your code.Superstitionfreeblog (talk) 13:37, 15 October 2024 (UTC)
Using Fasm or Nasm
While I was working on a subleq interpreter based on the pseudocode from wikipedia, I noticed that by modifying the assembly syntax that's usually used for subleq code, I can get nasm or fasm to build a binary file that can be read directly into memory by the interpreter or wrapped into a standalone executable.
Here's the Hello code from the main article modified to be assembled by fasm.
; Output the character pointed to by p.
db a, a, $+1
db p, Z, $+1
db Z, a, $+1
db Z, Z, $+1
a: db 0, -1, $+1
; Increment p.
db m1, p, $+1
; Check if p < E.
db a, a, $+1
db E, Z, $+1
db Z, a, $+1
db Z, Z, $+1
db p, a, -1
db Z, Z, 0
p: db H
Z: db 0
m1: db -1
; Our text "Hello, world!\n" in ASCII codes
H: db 72, 101, 108
db 108, 111, 44
db 32, 87, 111
db 114, 108, 100
db 33, 10
E: db E
This is 8 bit code because my working interpreter only interprets 8 bit code (for now). If you run this through nasm, it interprets the $+1 differently. Apparently nasm interprets $ to be at the beginning byte on the db line. So it would be $+3, not $+1. I also think if you used bigger words, you'd need to adjust that number to reflect that. It works for 8 bit code, though.
~$ fasm hello1.subleq hello1.sub flat assembler version 1.73.30 (16384 kilobytes memory) 2 passes, 54 bytes. ~$ hexdump hello1.sub -C 00000000 0c 0c 03 24 25 06 25 0c 09 25 25 0c 00 ff 0f 26 |...$%.%..%%....&| 00000010 24 12 0c 0c 15 35 25 18 25 0c 1b 25 25 1e 24 0c |$....5%.%..%%.$.| 00000020 ff 25 25 00 27 00 ff 48 65 6c 6c 6f 2c 20 57 6f |.%%.'..Hello, Wo| 00000030 72 6c 64 21 0a 35 |rld!.5| 00000036 ~$ subleq hello1.sub Hello, World!
Superstitionfreeblog (talk) 22:56, 13 October 2024 (UTC)
- In nasm you can probably play around with macros and get closer to the original syntax.
%define subleq(a, b, c) db a, b, c
%define next $+3
%macro subleq 3
db %1, %2, %3
%endmacro
- I'll play around with it some more. Superstitionfreeblog (talk) 23:48, 13 October 2024 (UTC)
My Subleq Interpreter
I'm as done as I'm going to get with my Subleq interpreter. It's only an 8 bit interpreter, so it's not very impressive. I've posted the source code on my user page. I'm either going to work on a Super Stack! compiler or a 64 bit/ floating point subleq interpreter. Superstitionfreeblog (talk) 06:59, 1 November 2024 (UTC)