ELIZA is Turing Complete | Hacker News Reader

ELIZA is Turing Complete

sites.google.com

72 pointsabrax314149 comments

The corecursive podcast recently had an excellent episode about the history around Eliza: https://corecursive.com/eliza-with-jeff-shrager/

I’ll second this. I listened to it twice. Hoping he does a follow up about it since the updates.

For more info on ELIZA: PAIP Chapter 5. ELIZA: Dialog with a Machine [1].

1: https://github.com/norvig/paip-lisp/blob/main/docs/chapter5....

> Hello, I am Eliza. I'll be your therapist today.[0]

[0] https://web.njit.edu/~ronkowit/eliza.html

Huh. Guess i found out why the game with the same name by zachtronics is named like that.

Highly recommend it btw. I'm not too much of a story-driven games person, but Eliza is contender for the best game i've ever played regardless, despite its simplicity.

There's a whole website dedicated to it, and yet I fail to find any explanation of what the hell Eliza is on that whole website.

Sharing basic background information should be mandatory for niche topics on HN.

It is a chatbot built in the 60's (!) that can respond based on simple rules (in the "scripts" the article is talking about).

https://en.wikipedia.org/wiki/ELIZA

It’s a Turing Machine interpreter written in the 1960s (!) that someone figured out could be used to build chat bots.

I admit that I am a skeptic, but my first try [1] gave an intriguing response, so I will continue playing with it.

[1] https://galactica.org/?prompt=what+is+the+relationship+betwe...

You commented the wrong article

It's referring to the ELIZA scripting language, not the original "therapist" interface. A programming language being Turing-complete isn't really news, it's... the main point, unless you are intentionally trying to avoid being Turing-complete.

I kind of assumed this was leading up into an overly-engineered joke about Eliza passing the Turing test.

Context on the therapist interface?

> A programming language being Turing-complete isn't really news, it's... the main point, unless you are intentionally trying to avoid being Turing-complete.

For example, Bitcoin "smart contracts" are intentionally not Turing-complete, and there are not per-opcode costs like there are for EVM and eWASM (which are embedded in other programs than Ethereum)

"The Cha Cha Slide Is Turing Complete" https://news.ycombinator.com/item?id=32477593 :

> Turing completeness: https://en.wikipedia.org/wiki/Turing_completeness

> Church-Turing thesis: https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis

Halting problem: https://en.wikipedia.org/wiki/Halting_problem :

> A key part of the proof is a mathematical definition of a computer and program, which is known as a Turing machine; the halting problem is undecidable over Turing machines. It is one of the first cases of decision problems proven to be unsolvable. This proof is significant to practical computing efforts, defining a class of applications which no programming invention can possibly perform perfectly.

Quantum Turing machine > History: https://en.wikipedia.org/wiki/Quantum_Turing_machine :

> [...] any quantum algorithm can be expressed formally as a particular quantum Turing machine. However, the computationally equivalent quantum circuit is a more common model.[1][2]

> History: [2005] A quantum Turing machine with postselection was defined by Scott Aaronson, who showed that the class of polynomial time on such a machine (PostBQP) is equal to the classical complexity class PP.

Complexity Zoo > Petting Zoo > {P, NP, PP,}, Modeling Computation > Deterministic Turing Machine https://complexityzoo.net/Petting_Zoo#Deterministic_Turing_M...

When I read the title, I too assumed it was about dialectical chatbots and - having just read turtledemo.chaos - wondered whether there's divergence and potentially infinite monkeys and then emergence of a reverse shell to another layer of indirection; turtles all the way down w/ emergence.

Yeah the title is misleading, I clicked on it assuming some monumental discovery had been made that I missed being a huge fan of GOFAI.

> Last updated 2022-14-12; Originally published 2022-11-12

There seems to be a typo in the date.

This is probably a nonstandard variant of European date order, yielding YYYY-DD-MM.

Usually when the year goes first or when there are hyphens as delimiters, it's an ISO 8601-style date (YYYY-MM-DD). However, Europeans often write DD/MM in other contexts, so the habit could transfer over when writing the year first, even though there's no standardized format that does this.

A one character typo seems more likely, than a non-standard date format for two dates in the future being used as timestamps.

Yep. It should be 11 not 14. I'm pretty sure it is because I did this often with keypad which 1 and 4 is vertically neighbored

More likely that the intended change was 2022-11-12 -> 2022-11-14, but edited the 11 instead of the 12.

Well, no, because it's not December yet. Pretty sure it's just a typo on the ISO date format.

For all we know, the author knows the last update date in advance (:

Oh, I missed a very important part of what people found surprising about these dates!

Ah, the Europeans and the slip-ups we imagine they commit using date formats we haven’t seen... before realizing that it’s not December yet.

> Europeans often write DD/MM in other contexts

Correction: Every country except the US (not counting the ones that use YYYY/DD/MM, such as Japan).

> Every country except the US (not counting the ones that use YYYY/DD/MM, such as Japan).

What? Japanese dates are always year-month-day, with slightly different separators. More generally the date notation tends to strongly reflect how it is spoken (e.g. "1st January 2023" becomes "1/1/2023") and there are enough countries where you never put day before month.

> Japanese dates are always year-month-day

Ugh, of course. That's a typo.

> the date notation tends to strongly reflect how it is spoken

Why does it differ between English speaking countries, then?

> Why does it differ between English speaking countries, then?

Because they speak differently? I would expect "November 17, 2022" spoken as "November seventeenth, twenty twenty-two" vs. "17 Nov 2022" as "seventeenth of November, twenty twenty-two". Wikipedia [1] does say that the latter DMY form recently arose possibly in order to resolve ambiguities and the spoken form is less common, but I expect it to be more frequently spoken after enough years of usage.

[1] https://en.wikipedia.org/wiki/Date_and_time_notation_in_the_...

One might guess that the author has a numpad on their keyboard, perhaps.

Duh-oh! Fixed. Thanks!

I vote for this mysterious month of Duodecember to remain standing.

At first, I thought it was referring to the conversation program, Eliza.

Then I thought it was referring to a programming language, Eliza.

Now I think it is referring to a modern programming language created to replicate the implementation of the conversation program, ELIZA.

The whole thing could have been far less confusing if:

1. The page provided more context about what ELIZA is.

2. If ELIZA is indeed a programming language (a Lisp?) inspired by the original ELIZA, it would be a good idea to give it a different name.

Anyway, it was frustrating to read this page so I have stopped.

I believe the article refers to the conversation program Eliza, but whose classic pattern-response database is replaced with different content. Plus there must be some feedback to close the loop; i.e. Eliza's output must be fed back to it as input.

Eliza is a kind of term rewriting system; it matches sentence patterns, and generates responses, using some of the matched content.

An iterated term-rewriting system can be Turing complete.

> Plus there must be some feedback to close the loop; > i.e. Eliza's output must be fed back to it as input.

Actually, the whole process takes place inside the rewriting system recursively.

The page says " ELIZA script, conforming to the specification given by Joseph Weizenbaum in his famous 1966 CACM paper".

https://sites.google.com/view/elizagen-org/about

And https://sites.google.com/view/elizagen-org/eliza-related-res...

says

> Weizenbaum, J. (1966). ELIZA: A computer program for the study of natural language communication between man and machine. Communications of the ACM, 9, 36-45.

> This paper remains under ACM copyright, and so is inaccessible, except to members or for purchase. However there are numerous versions of the PDF online

It looks like ACM has open-accessed this paper.

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

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

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.

We could use this TM to implement a lisp then run the lisp Eliza and run this TM on that, then implement a 7090 emulator on that TM and bring up MAD-SLIP and ELIZA on that, and then bring up a Godel coding engine on the TM running on that, thus creating an extremely slow turducken of Church, Turning, Weizenbaum, Godel, Chomsky, and McCarthy.

Don't forget to implement a character based version of Spacewar! on top of it, as a little nod to Steve Russell for implementing Lisp (and relying solely on S expressions). :-)

Reply on news.ycombinator.com