intro

nkov is a simple, star-free, nondeterministic esolang, based off markov chains and byte-pair encoding.

~~ an implementation of how the ladybug from the [ladybug clock puzzle](https://inv.nadeko.net/t3jZ2xGOvY9) would move on a 5-houred clock
~ this is her going forwards,
51
12
23
34
45
~ and her going backwards
54
43
32
21
15
~ we place her on the top of the clock
5

how it works

programs are a list of statements, separated by newlines. statements have two parts to them; their rule and their end. everything except the last symbol of a statement is referred to as its' rule, while that last symbol is its' end. statements which start with a ~ are comments.

when a program runs, nkov checks each statement to see if its' rule matches the end of the current state. when it does, its' end is appended to the state, and the process repeats. when none of the rules match, the line of execution that state belongs to stops.

when multiple statements match a given state, nkov branches its' line of execution between them, evaluating each one separately in order of when they were matched.

when the fluff option (-f) is chosen, the number of statements that a certain line of execution has gone through is represented by the indentation of its' printed state. the number besides said state (excluding the starting one) shows which statement had matched it, starting from 0.

properties

proven

1. an extension of nkov which allowed statements to have ends longer than one symbol would have equivalent computational power to vanilla nkov, but would be (at most) linearly more expressive, relative to how long said ends are.

for any statement(s) of the form a|xyz...w, where a is the rule and xyz...w is the end, you can turn it into the list of rules aX, Xy, XY, Yz, YZ, ..., ...w, where X, Y, Z, etc., are symbols not already used by the program. then, you can duplicate each statement with xy, xyz, etc. in its' rule, and substitute each occurrence of them with Xy, XYz, etc., respectively.

2. an extension of nkov which allowed statements to have rules refer to earlier parts of the state, relative to the end, would have equivalent computational power to vanilla nkov, but would be (at most) exponentially more expressive, relative to how many symbols are used in the program to the power of how far back the rule looks.

for any statement(s) with a rule of the form a*Nb, where *N specifies to look back N symbols into the state, and a and b are the surrounding parts of the rule, you can turn it into the list of rules a...b, where each ... corresponds to each N-symbol-long combination of every symbol used in the program respectively.

3. an extension of nkov which allowed statements to have rules refer to earlier parts of the state, relative to the start, would not have equivalent computational power to vanilla nkov.

for any statement(s) with a rule of the form @Na, where @N specifies to match a from symbol N in the state, you can turn it into the list of rules *Na, *Na*1, *Na*2, etc., for each state size where the position of a would be 0, 1, 2, etc. symbols away from the end of the state. since this would obviously entail an infinite number of rules, this means that this extension would be infinitely more powerful than vanilla nkov.

unproven (please help prove/disprove these if u'd like)

1. for any given file, it is probably not a valid nkov program; that is, nkov will probably not match a single rule of any of its' statements to its' starting state.

2. a restricted version of nkov which allowed only 2 symbol long statements would have equivalent computational power to vanilla nkov.

but why?

it's fun :3

todo

• an examples folder