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