Talk:Siterip

Syntax validity

I was trying to follow this through as it looked like an interesting Gödel numbering of bf that skipped syntactically invalid programs, but there's something up with the definition of 'valid' given the examples. +[-] is syntactically valid, with length 4 and halts in 4 ticks, but it's not on the list before the length 5 items. Also +[.] is syntactically valid, but non-terminating, I'd still expect to see that before the length 5s if this language were Turing Complete. It looks like loops are only possible with user input, since ,[.] = 330 is ok. Anyway, it's an interesting idea. It got me thinking whether there is a way to convert from this to other bf numbering schemes, but I think there's a problem with the syntax definition. I'm not necessarily advocating you should change the interpreter, the language could be fine as is, but the description and TC statement might need updating. Maybe it is still TC with user input, but I don't know whether ,[+[]] is valid Siterip or not. Salpynx (talk) 09:48, 12 March 2020 (UTC)

I'm glad that someone finds this language interesting. Program +[-] halts after 5 ticks, because ] always unconditionally jumps to the matching [. The actual index of that program is 16850. You can find the list of first 104007 programs here.

Program +[.] is not on the list, and it will never be, because it does not terminate on the empty input.

The language is Turing-complete, because the list is formed based on the halting time for the empty input. How data will be encoded and passed to the program is a matter of convention. For example, brainfuck has no way of distinguishing between NULL-characters and EOF, but they can still be encoded by various escaping mechanisms. Since all Siterip programs must halt on empty input, we can use the I/O convention of ignoring the first input character.

Any brainfuck program can be converted to Siterip program like this: ,[bf_program[-]]. It reads a single character (byte) from the input. If the byte is 0 (empty input), then halts (after exactly 2 ticks). Otherwise, executes the bf program exactly once (but the first character is already read, so we can artificially prepend a character in the Siterip input - as said, that is a matter of convention and input/output data interpretation).

"It looks like loops are only possible with user input" - No, actually loops are possible, but as explained above, ] takes one extra tick.

As for ,[+[]] - it is a valid Siterip program and its index is 4980 (it can be found in the longer list provided above).--Hakerh400 (talk) 14:13, 12 March 2020 (UTC)