parsing regex with HTML
it's (still, always, will never not be) crazy to me that two finite automata are reducible to one finite automaton but that two stacks is a turing machine.
but hmmm.......one stack's series of operations will always necessarily conform to the paired push–pop protocol. what is the "series of operations" for two?
well, imagine two work for some time, and each produce their own intermediate state (and allow negative push/pop). then the two are compared somehow (?)
why does single-stack paired push/pop achieve immediate solvability? because any previous intermediate state can be converted to any desired final state, by (if necessary) popping everything off then popping exactly the required order back on.
why does dual-automaton reduce? well, we can reframe it as "cartesian product of states, both moving at once". to transition to the desired final state from any intermediate state, each constituent automaton independently makes the same moves it would have alone. there is no move together that escapes the individual constraints, or vice versa.
two-stack with only one symbol is equivalent to one-stack one-sym i.e. an integer
in the case of overlapping stack syms (assume binary for both) the two may produce intermediate states that do not "unzip" or "match up" cleanly
oh oh oh i get it! (?)
the two stacks start from some left and right boundary towards each other in the center. on adjacent input indices, they have each now independently built up a stack (a bit string).
two interpretations:
(1) [adversarial] no matter what one stack does to achieve a desired final state, the other can thwart it. this is clearly true even if they both start with empty stack, and both decisions are made simultaneously.
(2) [goal] the desired final goal is to achieve a specific bit string composed of the left and the right stack's concatenated 1/0 contributions (ignore negatives).
the actual tape machine reduction (which was a challenge problem from jeremy spinrad to me many years ago, and which i just now discovered), is very similar to the above idea, but with the goal to produce a specific tape state.
so both come in from each side, generating the appropriate tape marks, and meet in the middle. however, the head of the tape machine must be at the correct index! but this is simple, by just identifying the distance from each boundary to the central head, and performing only up to those pushes
recall "stack cycles"—stack increments in such cases arrive in units of the stack diff corresponding to the path traced by a traversal of any of the currently active cycles for this point.
let's consider simplified: single stack sym. regardless of diff lengths per cycle available on either side, the two sides can match up: either one diff is an integer multiple of the other, hence match, or diffs are not aligned, which upon repeated addition will match (least common multiple).
the goal in the stack cycles construct is to match the negative of the other's state, hell or high water.
unlike the repeated addition case, the existence of a least common multiple is not guaranteed when consecutive bits (stack syms) do not always share a "color" [only a negated form of the same stack sym will cancel out a stack push, and only if both stack elements are each at the top of their stack]
"match the negative"—false. goal is to construct a given stack diff (sequence of polarized stack syms) separating the two cyclic nodes, by some in-order, one-at-a-time selection of left cycles (pushing more from left) and right cycles (pushing more from right)
so first off, this "stack diff" concept seemed reasonable enough at first, but this construction of "colored" bit strings is just such a ridiculous mathematical object
and the only way to reduce the length of a multicolored bit string is by matching the negation of its top symbol, repeatedly. this weirdly sounds like cryptography now
oh, what if we generate some sequence of cycles from both sides (cycles may pop), then concatenate the left stack diff (from left) with the right (from right), and removing the gap separating the tops of both stacks (which are now adjacent; if stack tops negated each other, pop them off pairwise until stable). this results in an unbroken contiguous multicolored bit string.
i wanna extract the colors. what does that achieve? are they independent?
i would suspect stack cycles can be constructed so that intermediate popping occurs to varying degrees, so consecutive colored bits would not correspond to the cycles. also implies that cycles should incorporate the same pairs of consecutive polarized stack syms at multiple points along the same or different cycles.
so not independent—in fact, deterministic. perhaps we just have two colors (orange/blue) and the orange ones are shifted to the left to produce the final bit string, which is clearly some sort of checksum
if anything, it's a randomness generator
there's also this matter of the two halves coming together. certainly the left half and right half could compute their orange and blue bit strings entirely independently. then, a = left's orange | right's blue, b = right's orange | left's blue. actually, let's intersperse the bits that form a and b, not merely concatenate. c = a | b then.
i suspect the ratio of input cycles selected => approximate length of output could be tuned to achieve a desired output length—but that assumes uniformly randomly distributed input cycle selections!
certainly the negatives of the cycle diffs could be selected from too. perhaps the opposing side would select from their own cycle diffs and the negatives of your side.
ok, what if the stack diff cycles on either side were neither random nor secret but instead constituted the whole set of permutations of polarized stack syms of length n > 0. but their order gets randomized (and then only the first k cycles taken). that can be used to produce nearly arbitrarily length-extending and length-reducing forms (log_4(m) at min, where m is the # of bits used to select).
and what if zero bits enabled the reversed negative of the indexed stack cycle to be pushed (onto the bottom of the opposite stack)?
i have been trying to make this invertible but i think that's the point of the polarized stack syms!
can i make it even less invertible?? can i increase the range of the negated stack syms beyond the top alone? can i apply negation alongside activated cycles from this round? (i.e. for two cycles both activated by a bitwise 1 this round, can negation apply up–down?)
i think the reason dh/modular exponentiation is capable of providing a keypair is because of its commutativity, which is a very special thing about it
so summary:
- a multicolored bit has orange/blue parity and 1/0 parity
- consider all permutations of rods of multicolored bits length n (4n such permutations i think?)
- randomly select k from (strictly ordered) permutations: these are the rows
- given a k-bit value, activate the 1 rows (intersperse the multicolored bits) and negatively activate the 0 rows (same, but negated & reverse order multicolor bit rod values)
- concatenate c = 0 | 1 (the interspersed results of both row categories)
- shift orange bits to left, blue to right
c is the result of a single k-bit value (k * n multicolored bits in length).
this approach can be used with multiple sets of rows of varying parameters (if k is the same, the same input can be muxed—k can instead be striped along the row inputs, but this seems like a bad idea). the result of multiple rows is to concatenate the results c = c_1 | c_2 | c_3 (orange bits always shift left—this is an associative operation).
orange and blue bits (or further coloration) may also be matched with the non-matching color bits of other sets (e.g. c_1(orange) || c_2(blue), where || refers to interspersing). while the relative order of sets should be immaterial as long as sets themselves are secure (unproven), this is one approach enabled by the multicolor bit methodology.
an alternative approach with multiple sets is to perform c = 1 | 0-, where 0- consists of the 0-activated rows from the set one to the right (wrapping around at far left). this may be more consistent to do even with only one set too.
if a negated stack symbol becomes adjacent to the positive form of that same symbol, the two should annihilate (how often will this be? what if we choose # colors = 2i?)
original version had varying-length cycles (by bit index of input k), as well as a second set mirrored to face the first set. mirroring and negating seem fine, but generally choosing k of 4n permutations randomly without replacement will be more significant.
notably the undecidability element of chaotic orbits around stack cycles is now gone, but undecidability isn't needed for a CSPRNG. i do very much like the stackable nature of multiple stack cycle sets, and also the scalability to circumstance by choosing k or n.
i have never once believed DH/relentlessly repeated modular exponentiation was safe for CSPRNG—you can do it a few times but not repeatedly, the generator graph curls into a little circle.
i have no clue if this is safe. i'm pretty sure i will need to demonstrate NP-completeness reduction (i think i mixed up n and k too, bother). i think boolean SAT will probably work for the portion that tries to keep the initial choice of k permutations secret, even knowing the value of the input k.
if so, then do we really need the multicoloration at all? it reduces our k-bit efficiency by log 2 (we will only require half as many bits to iterate the rng), and if we're hoping to encrypt k, we probably need more rounds than just one.
i think the number of bits k is actually the cycle index and 2k is the cycle length and i can't remember whether it's ok to just go in sequence or whether i will need to sprinkle in some randomness to fill up the k bits for the next execution
that sounds more correct, i'm pretty sure with a CSPRNG you really can just keep going and going and i seem to recall a paper on indexable CSPRNG saying it was cool
this feels way too easy i probably fucked up time for pizza
i think "linear language" is a better name than "finite-state language", because the matching is literally linear time and because there are no loops