Talk:An Odd Rewriting System

Implementation in Haskell

I implemented an An Odd Rewriting System interpreter in Haskell, in order to better understand the language. It doesn't implement parsing or the halting symbol. It can be found here. --Chris Pressey (talk) 12:48, 26 July 2019 (UTC)

Towards a non-exponentially-slowing-down simulation of a 1D-1D-CA

I note that in the Cwg example, the number of odd symbols at each step is

[1,2,1,4,2,2,1,8,4,4,2,4,2,2,1,16,8,8,4,8,4,4,2,8,4,4,2,4,2,2,1,32,...]

The parity of these numbers being

[1,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,...]

Is it fair to say this is an exponentially-slowing-down "master clock" driving the rest of the simulation? And that the rest of the simulation runs on its own hierarchy of clocks that are "nested" inside this master clock?

One could make a master clock that goes at a steady rate. The remainder of the data string would be, in essence, a restricted 1-dimensional 1-directional CA. (1-directional because the only context available to a symbol is what's to the left of it.) So the remainder of the data string is made up of "cells". To account for parity, the cells could be of alternating types: OEOEOE... The intent of this would be to get each cell to have the same behaviour, despite having a different number of neighbours on its left. Cells can't delete themselves or it would mess everything up, probably. But there has to be a way for a new cell to grow on the right. The rightmost cell could be special this way. The chain of cells might as well grow on every clock tick. It can grow by two cells on every master clock tick, for that matter, just to make sure it exceeds the "speed of light" of the main automaton. so: ...OEOET becomes ...OEOEOET in the space of a single master clock tick.

The cells themselves need to be finite state machines that transition based on parity on their left, and communicate their state by altering the parity on their right.

A big hurdle seems to be that the cell can't see the actual state of the neighbour on its left, only the parity of it. Could you get them to communicate their state by synchronizing? Say each cell can be in one of N states. Split up the master clock into N segments. Have each state only "listen" to the left during one of the segments (but "broadcast" to the right during all(?) segments). Since N is finite and fixed, the master clock can still run at a steady rate.

There may certainly be some detail standing in the way, but to me this sounds plausible. What do you think? Have I missed something crucial? --Chris Pressey (talk) 13:38, 26 July 2019 (UTC)

So the basic problem here is that all the symbols update simultaneously, so it's hard to create a symbol that alters the parity on its right in a predictable way. The symbol might decide "I want symbols on my right to see even parity next step" or "I want symbols on my right to see odd parity next step", but in order to do that, it needs to change its own parity to its own input on the next step, or the inverse of its own input on the next step, respectively; on the next step, the symbol to its right will see a combination of its parity and the parity of everything to its left. (It can't do that because it only has access to its input on the current step, it doesn't have information about what input it will get in the future.) You can work around this by adding additional symbols whose job is to predict what will appear on the left and compensate for it, but that causes an exponential blowup.

Being unable to see the actual state of the neighbour on the left is not a major problem, incidentally, because you can effectively produce a multi-bit parity via using symbols that produce a string of parities of fixed length (finite state machines can do that easily). --ais523 22:33, 26 July 2019 (UTC)

The way I see it, you overcome the difficulty you refer to by creating multi-symbol state machines that always assume that the parity on their left is even, *until* such time as they get an odd parity, which they interpret as a "clock tick" which causes them to advance their state. All of the processing a state machine needs to do, it needs to get done before the next clock tick (but you know the period and it's finite and so is the machine so that's fine.) The symbols internal to the state machine can account for any parity changes internal to the state machine (the designer knows exactly what's going on inside it), and the rightmost symbol can transmit odd or even parity to the state machine on its right as needed. (But the rightmost symbol should only communicate an odd parity to the right, as a momentary pulse when it's time for the cell on the right to expect a clock tick.)

I agree with the statement in your second paragraph but instead of "a string of parities of fixed length" I would describe it as "a fixed-length sequence of parities through time". So a state machine has behaviour like, "If I see an odd parity at phase 3 of 8 in the clock cycle, that means my left neighbour is in state #3, and I should respond appropriately based on what state I'm in; and if not, wait for the next phase."

A few minor points:

• I don't actually know if there are any 1D-1D-CA's that are useful for a TC proof -- I'm just trying to get a reduction to something that isn't exponential.
• What I'm talking about seems not dissimilar to various "1-wire protocols" seen in electronic engineering.
• Lastly, the state machines I'm describing might involve more symbols than there are lowercase glyphs in Unicode. (I imagine that you don't really intend that to be a limitation, of course, but still, it seems worth noting.) --Chris Pressey (talk) 08:44, 29 July 2019 (UTC)

OK, well, after a sleepless night, I can see more clearly why it's a difficult problem, now. I'm still not convinced it's impossible to devise a communications protocol that works under these conditions, but it's certainly beyond my ability. I admit defeat. --Chris Pressey (talk) 07:25, 30 July 2019 (UTC)

One-dimensional one-directional cellular automaton = 2C (which, probably not coincidentally, was created to prove AORS Turing-complete). It uses a left-neighbourhood of more than one character, but you can reduce it to one character using the usual trick (of encoding the states of n adjacent symbols into a single symbol). For what it's worth, the one-directionality turns out not to make a difference in practice, because you can just have the entire state of the CA move a sufficiently far distance to the right on every cycle that all its inputs are on its left. Ais523 non-admin (talk) 11:59, 2 August 2019 (UTC)

what about minsky machines?

don't they have the same problem? for e.g. a shift right instruction, they need to decrement a number of times that is exponential to the size of the tape they are simulating... right? or am i missing something and this simulation is slow enough to be a problem worth documenting while minsky machines don't? --Pro465 (talk) 17:06, 28 May 2023 (UTC)

The problem with AORS is worth documenting because it's a) unexpected and b) not obvious that it's real (there might be some solution available). For Minsky machines, an exponential slowdown in terms of number of state transitions is expected. (Additionally, for a Minsky machine, an optimising interpreter can easily implement tape-like behaviour in quadratic time, e.g. my Ratiofall interpreter for The Waterfall Model can do that, and there's probably some way to optimise further so that it works in linear time. The trick is to recognise that the program is in a loop, and simulate the effect that the loop would have rather than simulating all the iterations individually. Of course, it's quite probable that something similar is possible for AORS too.) --ais523 12:41, 30 May 2023 (UTC)

oh right, thanks! i was worried that i was misunderstanding something about minsky machines, because all the articles about minsky machines that i've read had not mentioned its time complexity. --Pro465 (talk) 11:06, 31 May 2023 (UTC)

what is actually a symbol in AORS?

in the syntax section, it is mentioned that symbols are represented using unicode characters, but according to the rust doc for char type(i was planning on implementing it using rust chars):

The char type represents a single character. More specifically, since ‘character’ isn’t a well-defined concept in Unicode, char is a ‘Unicode scalar value’.

so i wondered if using char is appropriate here. thanks --Pro465 (talk) 11:00, 31 May 2023 (UTC)

By "character" the spec is talking about Unicode codepoints / scalars, so Rust char is suitable, but might be inefficient: given that you're scanning the entire string at every step anyway, it probably makes more sense to use String (iterating with the .chars method, and writing the resulting characters to a new String). In Rust, String is much more memory efficient than Vec<char> is. --ais523 15:03, 1 June 2023 (UTC)

i only needed to know whether it was suitable for the match part to be represented as a single char, but thanks for the additional bit of information. found it very insightful! --Pro465 (talk) 15:56, 1 June 2023 (UTC)

btw, i completed the interpreter, where do i post it? here? separate page like Odd.hs? github? github gist? --Pro465 (talk) 16:36, 1 June 2023 (UTC)

Normally what people do is to host the interpreter wherever they want (GitHub, their own website, etc.) and link to it from the wiki. Some people prefer to post their interpreters directly to the wiki instead, but doing that means that you lose copyright control over them (because they become public domain). --ais523 14:21, 2 June 2023 (UTC)

i posted it directly here. thanks for the help! --Pro465 (talk) 17:29, 2 June 2023 (UTC)

contradiction in computational class proof?

unless I am misunderstanding something, does not the following two sentences contradict one another?

1. Now, imagine that this program were modified to only update on every second cycle (via giving each character an "alternative version" that doesn't update, analogous to x and ẋ in the program above); that means that oddness on the "off cycles" would not affect the behaviour of the program.
2. specifically, the state machine would remember whether it had observed oddness on the previous 2s off cycles, where s is the maximum length of a search string in the 01-2C program, in addition to maintaining the previous behaviour of the state machine

or does "maintaining the previous behaviour" mean an oddness in the off-cycles would (somehow) both affect program behaviour AND also not? --Pro465 (talk) 12:30, 2 June 2023 (UTC)

It's suggesting making two separate changes to the program. The first change introduces extra cycles that can be used to transmit information, without changing how the existing program behaves. The second change makes use of those cycles to transmit information; this still doesn't change the existing behaviour of the program (because the first change was designed so that oddness on off cycles doesn't affect that) but it allows the program to exhibit new behaviour in addition. --ais523 14:18, 2 June 2023 (UTC)