This forum is closed to new posts due to low activity and a deluge of spam. It is kept online as a static historical record. If you want to read about or discuss esoteric programming languages, the Esolang wiki is the place to go. An archive of the forum is available.

Turing-completeness proof? (4)

1 Name: Nortaneous : 2009-02-02 05:58 ID:G/7d0bkk

For this language:

take first two hex digits and add them to the current tape cell (it operates on a tape, just like brainfuck, and the cells are bytes, so the addition is mod 256), then if that's zero, jump to the absolute location given by the rest of the hex digits right before the next instruction (for example, +055 would add 5 to the current cell and jump to the fifth character in the source if the result came out to be zero)), then shift the pointer to the right, like brainfuck's >

<
same as brainfuck, shift pointer to the left

?
if the current tapecell holds a value that is not zero, jump to the location given by the hexdigits immediately following it (for example, ?23 would jump to the 35th (in decimal) character in the source)

An isomorphism proof would be easiest, I think, but I don't know of any other languages that use that loop structure. I tried coding a converter from brainfuck to this, but the loops are a bitch to do.

2 Name: Nortaneous : 2009-02-02 05:59 ID:G/7d0bkk

Well, I fail. That bullet point is supposed to be a +, if it matters at all.

Lame interpreter in BASIC here: http://openpaste.org/en/10930/ (code has an extension of .sfe)

3 Name: fizzie : 2009-02-02 08:54 ID:LWRBJfLj

Well, brainfuck conversion doesn't seem to be too difficult.

There's a converter (in Perl) at http://zem.fi/~fis/sfe.pl.txt -- it can optionally run the code it generates. I haven't tested it much, but hello world in brainfuck seems to work (although I'm sure this forum thing will mess the formatting here):

fis@eris:~$ echo -n '++++[>++++<-]>+[>>++>+>+>++<[+++++<]<-]>>>++.>-.-<++++..+++.>>--.+<<<.----->.---<[.>]' | ./sfe.pl convert
+010007<+01000f<+010017<+01001f<+000064<+00002f+010036<+01003e<+010046<+01004e<<+ff0057<?0028+000064<+00006c+010073<+000123<+000083+00008a+010091<+010099<+0000a1+0100a8<+0000b0+0100b7<+0000bf+0100c6<+0100ce<<+00010d<+0100df<+0100e7<+0100ef<+0100f7<+0100ff<<?00d8+00010d<<+ff0116<?007c+000123<+00012b+000132+000139+010140<+010148<.+000151+ff0158<.+ff0161<<+01016a<+010172<+01017a<+010182<..+01018c<+010194<+01019c<.+0001a5+0001ac+ff01b3<+ff01bb<.+0101c4<<<<.+ff01d0<+ff01d8<+ff01e0<+ff01e8<+ff01f0<+0001f8.+ff0200<+ff0208<+ff0210<<+00022e<.+000222?021a+00022e<

echo -n '++++[>++++<-]>+[>>++>+>+>++<[+++++<]<-]>>>++.>-.-<++++..+++.>>--.+<<<.----->.---<[.>]' | ./sfe.pl run
hello world!

I've been using 0-based indexing in the jump addresses in the generated code, which might not match that BASIC interpreter.

The conversion looks approximately like this (probably messed-up formatting here too, but it's in sfe.pl comments):

# + == +01{next}<
# - == +ff{next}<
# < == <
# > == +00{next}
# [foo] == +00{addr2}< |1 conv(foo) ?{addr1} +00{addr2} |2 <
# . == .
# , == ,

The |1 and |2 there in loops are the locations of addr1 and addr2.

4 Name: fizzie : 2009-02-02 08:57 ID:LWRBJfLj

Oh, the formatting markup description and the "preview" button would've been there under the "more options..." link. Oh, well. It didn't go so badly, although using a

monospaced code block

for those examples and the table would have been nice.

Name: Link:
Leave these fields empty (spam trap):
More options...
Verification: