Syntactic Confectionery Delight PerlMonks

Re^2: Turing completeness and regular expressions

by JadeNB (Chaplain)
 on Nov 28, 2009 at 17:41 UTC ( #809918=note: print w/replies, xml ) Need Help??

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/;
[download]```
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.)

Replies are listed 'Best First'.
Re^3: Turing completeness and regular expressions
by blokhead (Monsignor) on Nov 28, 2009 at 17:52 UTC
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).

blokhead

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

blokhead

Log In?
 Username: Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://809918]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (2)
As of 2021-05-12 05:15 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Perl 7 will be out ...

Results (124 votes). Check out past polls.

Notices?