All program data is represented as a single string. This string is repeatedly manipulated in a deterministic fashion according to rewriting rules of the form
A single step of computation rewrites the string according to the first applicable rule. If no rule can be applied to the string, the program halts.
Note that the left-hand side of a rule must match the entire string, not just a substring. For example, the rule
transforms "apple" into "orange", but not "1apple2" into "1orange2".
There are two types of variables that can appear in a rule, s-vars and m-vars. An s-var stands for any single character and is written by prepending a "^" to any character, while an m-var stands for any substring of zero or more characters and is written by prepending a "_" to any character. For example, the rule
duplicates the first character in a string. Here "^A" represents the first character, and "_B" represents the rest of the string.
M-vars are bound to substrings left-to-right, and always match the shortest possible substring so that the left-hand side matches the entire string. For example, the rule
transforms "aabb" into ",ab" and not "a,b".
A Sonata program is simply zero or more rules written on separate lines. Rules are searched from top to bottom. A program's input is the initial value of the string to be rewritten, and its output is the final value of the string if the program halts.
Sonata can trivially emulate any m-tag system. Since the set of all m-tag systems (for any m>1) is Turing-complete, Sonata must also be Turing-complete. For example, the program
a^X_Y->_Ybc b^X_Y->_Ya c^X_Y->_Yaaa
emulates the 2-tag system
a -> bc b -> a c -> aaa
which computes the Collatz sequence for some number n, written as n a's.