Re^2: Turing completeness and regular expressions

[JadeNB]

Probably not. You should be able to evaluate an SK-expression from the bottom up (instead of top-down) if it is fully parenthesized. Something like this:

s/\(S([^()])([^()])([^()])\)/($1($3($2$3)))/;
s/\(K([^()])([^()])\)/$1/;
s/\(I([^()])\)/$1/;

i.e., always evaluate the "innermost" expression, which will be the one without parentheses. I think something like this may work though I've not tested it.

I think that this does not work. For example, it does not reduce ((K((SK)K))K) to (SK)K (UPDATE: or, better, (((K((SK)K))K)x) to x).

Set up a recursive substitution to recognise functional equivalence of combinators (so that it could identify ``SKK and ``SKS as functionally equivalent).

Equivalent to the halting problem in the general case. Let an SK-expression simulate a Turing machine M on input x. Is it equivalent to the SK-expression that always returns true?

Yes, that's what I thought; but Stenlund provides a finite system of equations for deciding—well, something. I thought that it was functional equivalence, but I must have misunderstood. I'll look it up when I've got my copy. (Incidentally, the combinator is KK.)

[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.

But we both missed the obvious way to just use "plain" regex substitutions to simulate Turing-completeness: unrestricted (type-0) grammars. They are basically defined 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).

[JadeNB]

But we both missed the obvious way to just use "plain" regex substitutions to simulate Turing-completeness: unrestricted (type-0) grammars. They are basically defined 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).

I didn't know about this, but I'm not sure that it's quite right to say that I missed it completely; indeed, the two wodges of code I wrote are just implementing systems of re-writing rules, which it seems to me are the same as unrestricted grammars, and the way that I did it is with a substitution plus a finite look-up table (built into the string on which the substitution acts). Am I missing your point?

[blokhead]

Yes, you certainly were implementing essentially a type-0 grammar system the whole time. The point is that positively identifying it as a type-0 grammar gives a much clearer insight into your original question (do "plain" regex substitutions suffice to simulate Turing-complete behavior?) than going through SK/lambda as an intermediate step (which you found to require a little more care when simulating via regex substitutions). The theory of type-0 grammars says quite simply that there is a set of universal, plain regex substitution rules; in fact, as simple as you can imagine regex substitutions to be (s/fixed-string/fixed-string/). I didn't mean to imply that what you were doing was not an unrestricted grammar, just that we missed this "easiest" way to see the answer to that question in the original post.