Talk:Xeroxer

simplification

context: the following ideas were noted in the context of the original 3-argument version

i think this is too complex for a turing complete oisc. so, i will think and note some simplification ideas here when i get them. --Pro465 (talk) 11:04, 10 June 2023 (UTC)

1. we could go completely relative addressing, and remove the idx parameter. it would then copy from len positions back to this position, but I'm not sure if it would retain turing completeness. --Pro465 (talk) 11:53, 10 June 2023 (UTC)
2. thinking about it, we could have relative idx. it could then retain turing-completeness by always keeping the production table close. however we still have 3 params (which is what I'm trying to simplify, btw) --Pro465 (talk) 16:25, 11 June 2023 (UTC)

I've convinced myself that #1 does retain turing completeness. I am currently trying to implement collatz sequence in #1 to test the idea. --Pro465 (talk) 18:16, 11 June 2023 (UTC)

potential proof of Turing completeness

the following notes were made while i was trying to build a simulation of bi-tag system:

// a -> (0, |a|) a (|a| + 2, 0)
// e -> (0, j)
// p[b, e] -> copy(copy((0, l) edge) (k, 0) copy(copy(b) (0, j))) (0, m)
// p[b, c, e] -> copy(copy((0, l) edge) (k, 0) copy(copy(b) p[c, e])) (0, m)
// edge = (|a| + 2, 0) (0, |a|)
// k = |a| + 5
// l = |a| - |b| + 1
// |b| = |c|
// |a| - |b| < j < |a| + 1
// copy(a) = (0, |a|) a (|a|, 0)
// m - variable

i may complete the translator, in which case i will post it here. in the meantime, feel free to decode and/or implement it. --Pro465 (talk) 17:21, 13 June 2023 (UTC)

sketch of an Echo Tag to Xeroxer translation

lets introduce an intermediate language, we will call it X. X is similar to Xeroxer, in that it is an oisc and queue-based. however, its command is as follows:

(idx, len, offset) (copies instructions ip-idx..ip-idx+len (exclusive) and jumps to ip+offset+1

we can emulate it in Xeroxer by ensuring that there is:

1. a (0, len) at address ip-idx,
2. a (len, idx-len-1) at address ip-idx+len+1,
3. a (idx, offset) at address ip

(untested, may contain off-by-one errors)

this has many restrictions, but we can be sure that Echo Tag is simple enough to not require those advanced features to implement.

so, our program will look like this:

[prod]ss...s

where prod is the production rules and s are the data bits of the simulated ET queue. the bit immediately after the prod is the bit at the front of the queue. prod is just a lookup table with the last rule representing the current rule being considered.

we can now compile ET to X:

1. a 0 bit just copies firstly the last rule to the end, then the rest of the rules.
2. a 1 bit does the same, but copies the rule twice.

there it is. now most of the translation of X -> Xeroxer involves maintaining invariants, delaying execution until the invariant are upheld, etc. so its left as an exercise to the reader. --Pro465 (talk) 18:49, 14 June 2023 (UTC)

Output?

i just got this idea: what if we use the command "0 0" as a sign to output the previous instruction (encoded in unicode)? Thoughts? --Pro465 (talk) 10:44, 19 June 2023 (UTC)

minimum turing complete parameter bounds

based off the Echo tag to xeroxer translator, the maximum values for the translated UT19 program is 27281 and 27267 for the copy and jump parameters. these numbers could probably be lessened by a direct translation from tag systems to xeroxer, which I'm trying to build now. --Pro465 (talk) 10:17, 18 September 2023 (UTC)

done. and from that, the maximum parameters for copying and jumping seems to be 591, and 576 respectively. --Pro465 (talk) 18:16, 19 September 2023 (UTC)