Comment by masswerk | Hacker News Reader

Comment by masswerk | Hacker News Reader

Parent Full thread

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

  ; 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))
  )

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

So have

  (USAGE: PALIN A B B A ...)
  START

at the beginning and a MEMORY rule (must have exactly 4 entries) at the end:

  (MEMORY XYZZY
       (0 = A)
       (0 = B)
       (0 = A A)
       (0 = B B)
  )

:-)

PS: I'm not sure, if the initial welcome message is actually mandatory, but the MEMORY rule definitely is.

Weizenbaum says the list must be there, but may be empty: "Finally, the script writer must begin his script with a list, i.e., a message enclosed in parentheses, which contains the statement he wishes ELIZA to type when the system is first loaded. This list may be empty." page 42 of the 1966 CACM ELIZA paper.

And the MEMORY keyword "must be an ordinary keyword as well." So you'd need a (XYZZY ...) rule.

Also, the START symbol appears in the DOCTOR script, but is never mentioned in the body of the paper.

Another thing Weizenbaum doesn't mention in his description is the final empty list in the DOCTOR script. This does seem to be expected by the code.

I guess, some of these may have been artefacts from how the printout was produced. Notably, ELIZA was an extensible system, meant to start with a small script, to be extended progressively, and featured "live" editing capabilities. According to the 1966 paper, "START" is actually ELIZA's answer after returning from an editing session. And I wouldn't be shocked, if the final empty list had been placed there for convenience by the system.

Other: It has been a while, since I had a closer look at ELIZA, and I have to admit that I forgot most about the intrinsics of the MEMORY rule.

PS: An interesting feature of ELIZA in the context of problem solving may be that, if there is more than a single recomposition rule, ELIZA will cycle through them (e.g., alternating between two expressions.) This may allow for some interesting, even surprising, and still state-dependent behavior, kind of a "Moiré logic". :-)

I agree with you. I think the presence of START is accidental and is not supposed to be part of the script. The ELIZA code uses a Slip function called LISTRD to read the script rules one by one. If it reads an empty list it stops reading the script and begins the conversation. So I think the empty list at the end of the script had a reason to be there. Another accidental thing about the script in the CACM paper is that there are 6 duplicated lines, each one 34 lines from the previous one. I had not heard of Moiré logic. I'm contributing to a book about ELIZA and its legacy. No publisher yet. The editors may be looking for other contributors. I realize this is not much to go on, but say if it might be of interest to you.

Oh thanks, but I don't think that I have much to contribute. I had been musing about a faithful ElIZA emulation a few years ago, but ELIZAGEN put somewhat an end to this.

"Moiré logic" was a joke, meaning, an interference pattern caused by two layers of logical state.

Well, there's actually one thing, I can contribute: The famous photo of Weizenbaum on a terminal (sometimes attributed to the German magazine "Die Zeit") – e.g. here [1] – seems to show Weizenbaum on a Lorenz teletypewriter [2], so there is some probability to the photo actually having been taken in Germany.

[1] https://maeda.pm/2019/02/11/joseph-weizenbaum-humanist-techn...

[2] https://twitter.com/RetroWizzard/status/1419658098210451459 (1st image)

PS: You may find this one (my own doing) amusing: https://masswerk.at/eliza/

Thank you for the links. Lovely online ELIZA. I appreciate you responding.

Reply on news.ycombinator.com