note blokhead You may be right about bottom-up evaluation of SK expressions. Larger terms must be treated as first-class objects to be passed around, etc. <p> But we both missed the obvious way to just use "plain" regex substitutions to simulate Turing-completeness: [wp://Unrestricted grammar|unrestricted (type-0) grammars]. They are basically <i>defined</i> as the repeated evaluation of plain regex substitutions, and are Turing-complete. A universal TM converted to a type-0 grammar will only have a finite number of substitution rules, and you can simulate it with a substitution + finite lookup table (or a finite # of separate s/// statements). <!-- Node text goes above. Div tags should contain sig only --> <div class="pmsig"><div class="pmsig-137386"> <p> blokhead </div></div> 809842 809918