5 ms·

Well, this is quite a set of Russian dolls: 1) SLIP (Symmetric List Processor) is a collection of subroutines designed by Joseph Weizenbaum to be embedded in a

Well, this is quite a set of Russian dolls: 1) SLIP (Symmetric List Processor) is a collection of subroutines designed by Joseph Weizenbaum to be embedded in a higher order language 2) ELIZA is a program, also written by Joseph Weizenbaum, and a SLIP application, which reads in a set of rules, called an ELIZA-script (the best known of these scripts is the doctor/therapist script commonly associated with ELIZA), and matches any console input against these rules in order to produce a transformation as an answer. The general idea is to give the appearance of a natural language conversation program that may be operated from a terminal. 3) In order to do so, ELIZA (the program) exposes some SLIP functions to these rule sets (expressed in an ELIZA-script). Mind that these functions are quite powerful and general in nature. 4) Generally speaking, ELIZA (the program) matches words in the input stream against a list of keywords, which are associated with rules for matching certain text patterns and rearranging them into an output stream. (In other words, for the most part a usual ELIZA-script, like the doctor script, merely reflects the input in a transposed form. There are is no "understanding" involved.) 5) One of these rules in ELIZA's grammar is the "PRE" rule, which reorders and/or substitutes certain expressions in the input stream in order to feed the recomposed output into another rule. 6) By this, we can use ELIZA (the program) to decompose and recompose and reinterpret a given stream using a special set of rules, expressed in an ELIZA-script, until a terminal state is reached. (Which is the case, when the input stream has been transposed reiteratively to a terminal symbol recognized by a rule in our script.) 7) This is both surprising and not surprising at all. SLIP was written to provide general building blocks for a higher order language and ELIZA (the program) is such a language. ELIZA (especially its doctor script) was highly influential for mimicking quite successfully a natural language conversation in the mid 1960s. To do so, it directly exposed SLIP functionality to its scripts (rule sets). While not advertised by any means, it is not of great wonder that some of the generality of SLIP may be exposed by ELIZA's grammar. Notably, the "PRE" grammar was – according to Weizenbaum – introduced for economical reasons, not for extra logical functionality. However, there is more to it, as it "leaks" generality, by not only allowing us to recompose an input, but also allowing us to feed this output into another, specified rule, where it will be interpreted anew. This can be used to encode state and to repetitively interpret a stream with respect to this state until a terminal state (as the answer to a problem) is eventually reached. (There are, however, some technical limitations to the generality of ELIZA: e.g., keywords, which mark and group any rules, are hashed to 7-bit integers and there may be just 128 keywords and 512 rules in total.)

deleted 4y ago
[deleted]
zomglings 4y ago
Wow. Thank you, this was immensely helpful and informative.
- masswerk 4y ago
  Regarding Turing completeness: It may be of interest that the "PRE" rule allows us to both alter the tape (the input, we're processing) and to switch rule sets (as we are specifying a distinct rule for reprocessing). As rewriting also allows us to simulate the position of a read/write head (by inserting some reserved characters) and this may be matched by rules, as well, there are all the elements of a Turing machine. (Notably, this is not the only possible approach to problem solving that may be attempted using ELIZA. E.g., the palindrome problem used as an example in the article, doesn't require multiple sets of rules to incorporate state. We could do it also by simple reduction: If the input is a single letter or exactly two instances of the same letter {"A", "B", "A A", "B B"}, it's a palindrome, output this as the final answer. Else, if the first and the last letter are the same {"A … A", "B … B"}, discard them and redo with the remaining middle part. If this rule fails as well, it's not a palindrome, also a final answer.)
  - masswerk 4y ago
    ; Palindrome test by simple reduction ; "(0)" is a catch-all pattern ; "NONE" matches, where no keyword matches ; - ideal for help phrases (PALIN ((PALIN 0) (PRE (2) (=REDUCE))) ) (REDUCE ((A) (=TERM_TRUE)) ((B) (=TERM_TRUE)) ((A A) (=TERM_TRUE)) ((B B) (=TERM_TRUE)) ((A 0 A) (PRE (2) (=REDUCE))) ((B 0 B) (PRE (2) (=REDUCE))) ((0) (=TERM_FALSE)) ) (TERM_TRUE ((0) (WELL, THIS IS A PALINDROME)) ) (TERM_FALSE ((0) (NOT A PALINDROME AT ALL)) ) (NONE ((0) (TRY: PALIN A B A)) )
    - anthay 4y ago
      That's really cool. (The paper uses the palidrome example to try to demonstrate how a Turing machine might be encoded in an ELIZA script.) ELIZA scripts must begin with some opening remarks, e.g. (HELLO. PLEASE TELL ME YOUR PROBLEM), and they must have a MEMORY rule, e.g. (MEMORY PALIN (0 = 1) (0 = 1) (0 = 1) (0 = 1)).

deleted 4y ago

[deleted]

zomglings 4y ago

Wow. Thank you, this was immensely helpful and informative.

masswerk 4y ago
Regarding Turing completeness: It may be of interest that the "PRE" rule allows us to both alter the tape (the input, we're processing) and to switch rule sets (as we are specifying a distinct rule for reprocessing). As rewriting also allows us to simulate the position of a read/write head (by inserting some reserved characters) and this may be matched by rules, as well, there are all the elements of a Turing machine. (Notably, this is not the only possible approach to problem solving that may be attempted using ELIZA. E.g., the palindrome problem used as an example in the article, doesn't require multiple sets of rules to incorporate state. We could do it also by simple reduction: If the input is a single letter or exactly two instances of the same letter {"A", "B", "A A", "B B"}, it's a palindrome, output this as the final answer. Else, if the first and the last letter are the same {"A … A", "B … B"}, discard them and redo with the remaining middle part. If this rule fails as well, it's not a palindrome, also a final answer.)
- masswerk 4y ago
  ; Palindrome test by simple reduction ; "(0)" is a catch-all pattern ; "NONE" matches, where no keyword matches ; - ideal for help phrases (PALIN ((PALIN 0) (PRE (2) (=REDUCE))) ) (REDUCE ((A) (=TERM_TRUE)) ((B) (=TERM_TRUE)) ((A A) (=TERM_TRUE)) ((B B) (=TERM_TRUE)) ((A 0 A) (PRE (2) (=REDUCE))) ((B 0 B) (PRE (2) (=REDUCE))) ((0) (=TERM_FALSE)) ) (TERM_TRUE ((0) (WELL, THIS IS A PALINDROME)) ) (TERM_FALSE ((0) (NOT A PALINDROME AT ALL)) ) (NONE ((0) (TRY: PALIN A B A)) )
  - anthay 4y ago
    That's really cool. (The paper uses the palidrome example to try to demonstrate how a Turing machine might be encoded in an ELIZA script.) ELIZA scripts must begin with some opening remarks, e.g. (HELLO. PLEASE TELL ME YOUR PROBLEM), and they must have a MEMORY rule, e.g. (MEMORY PALIN (0 = 1) (0 = 1) (0 = 1) (0 = 1)).