14 ms·

ELIZA is Turing Complete

72 points by abrax3141 4y ago

gowld 4y ago
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.
- slongfield 4y ago
  I kind of assumed this was leading up into an overly-engineered joke about Eliza passing the Turing test.
- pyinstallwoes 4y ago
  Context on the therapist interface?
- westurner 4y ago
  > 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 https://news.ycombinator.com/item?id=32477593 : > Turing completeness: https://en.wikipedia.org/wiki/Turing_completeness https://en.wikipedia.org/wiki/Turing_completeness > Church-Turing thesis: https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis Halting problem: https://en.wikipedia.org/wiki/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 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_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.
- zshrdlu 4y ago
  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.
yvdriess 4y ago
The corecursive podcast recently had an excellent episode about the history around Eliza: https://corecursive.com/eliza-with-jeff-shrager/ https://corecursive.com/eliza-with-jeff-shrager/
- MR4D 4y ago
  I’ll second this. I listened to it twice. Hoping he does a follow up about it since the updates.
phoe18 4y ago
> Last updated 2022-14-12; Originally published 2022-11-12 There seems to be a typo in the date.
- schoen 4y ago
  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.
  - avgcorrection 4y ago
    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.
  - janzer 4y ago
    A one character typo seems more likely, than a non-standard date format for two dates in the future being used as timestamps.
    - stevefan1999 4y ago
      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
    - naniwaduni 4y ago
      More likely that the intended change was 2022-11-12 -> 2022-11-14, but edited the 11 instead of the 12.
  - ISV_Damocles 4y ago
    Well, no, because it's not December yet. Pretty sure it's just a typo on the ISO date format.
iLoveOncall 4y ago
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.
- danuker 4y ago
  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 https://en.wikipedia.org/wiki/ELIZA
- abrax3141 4y ago
  It’s a Turing Machine interpreter written in the 1960s (!) that someone figured out could be used to build chat bots.
zomglings 4y ago
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.
- kazinator 4y ago
  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.
  - abrax3141 4y ago
    > 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.
- lupire 4y ago
  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 https://sites.google.com/view/elizagen-org/about And https://sites.google.com/view/elizagen-org/eliza-related-resources 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
emmanueloga_ 4y ago
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.md https://github.com/norvig/paip-lisp/blob/main/docs/chapter5....
Maursault 4y ago
> Hello, I am Eliza. I'll be your therapist today.[0] [0] https://web.njit.edu/~ronkowit/eliza.html https://web.njit.edu/~ronkowit/eliza.html
- themoonisachees 4y ago
  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.
patkai 4y ago
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+between+classical+physics+and+polyphonic+music https://galactica.org/?prompt=what+is+the+relationship+betwe...
- deleted 4y ago
  [deleted]
- elcomet 4y ago
  You commented the wrong article

72 points by abrax3141 4y ago

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.

slongfield 4y ago
I kind of assumed this was leading up into an overly-engineered joke about Eliza passing the Turing test.
pyinstallwoes 4y ago
Context on the therapist interface?
westurner 4y ago
> 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 https://news.ycombinator.com/item?id=32477593 : > Turing completeness: https://en.wikipedia.org/wiki/Turing_completeness https://en.wikipedia.org/wiki/Turing_completeness > Church-Turing thesis: https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis Halting problem: https://en.wikipedia.org/wiki/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 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_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.
zshrdlu 4y ago
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.

yvdriess 4y ago

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

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

phoe18 4y ago

> Last updated 2022-14-12; Originally published 2022-11-12 There seems to be a typo in the date.

schoen 4y ago
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.
- avgcorrection 4y ago
  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.
- janzer 4y ago
  A one character typo seems more likely, than a non-standard date format for two dates in the future being used as timestamps.
  - stevefan1999 4y ago
    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
  - naniwaduni 4y ago
    More likely that the intended change was 2022-11-12 -> 2022-11-14, but edited the 11 instead of the 12.
- ISV_Damocles 4y ago
  Well, no, because it's not December yet. Pretty sure it's just a typo on the ISO date format.

iLoveOncall 4y ago

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.

danuker 4y ago
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 https://en.wikipedia.org/wiki/ELIZA
abrax3141 4y ago
It’s a Turing Machine interpreter written in the 1960s (!) that someone figured out could be used to build chat bots.

zomglings 4y ago

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.

kazinator 4y ago
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.
- abrax3141 4y ago
  > 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.
lupire 4y ago
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 https://sites.google.com/view/elizagen-org/about And https://sites.google.com/view/elizagen-org/eliza-related-resources 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

emmanueloga_ 4y ago

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.md https://github.com/norvig/paip-lisp/blob/main/docs/chapter5....

Maursault 4y ago

> Hello, I am Eliza. I'll be your therapist today.[0] [0] https://web.njit.edu/~ronkowit/eliza.html https://web.njit.edu/~ronkowit/eliza.html

themoonisachees 4y ago
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.

patkai 4y ago

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+between+classical+physics+and+polyphonic+music https://galactica.org/?prompt=what+is+the+relationship+betwe...

deleted 4y ago
[deleted]
elcomet 4y ago
You commented the wrong article