2

I was reading about tge Turing machine. I also came across with the Shakespeare programming language. After trying to understand the basics of the PL, I thought that it must be non-Turing complete. On some page I found out that I was wrong and Shakespeare is actually "turing complete".

I didn't find how can I create while loops or recursive calls in Shakespeare so I can't understand why it us Turing complete.

Will be glad for some explanation.

reinierpost
  • 5,509
  • 1
  • 21
  • 38
vesii
  • 223
  • 1
  • 7
  • 1
    Have you seen: https://cs.stackexchange.com/questions/2832/is-a-push-down-automaton-with-two-stacks-equivalent-to-a-turing-machine ? In given language you declare number of stacks to use, two will suffice. There are conditionals and goto instructions, so there are loops. – Evil Feb 23 '19 at 04:11
  • 1
    Loops in Shakespeare can be created with gotos. – Discrete lizard Feb 23 '19 at 09:33

1 Answers1

4

In that page, the snippet

Juliet:
 Am I better than you?

Hamlet:
 If so, let us proceed to scene III.

essentially means

if (Juliet > Hamlet) goto Scene III

This can be used to implement while loops. In pseudo syntax:

Scene II:
if (Juliet > Hamlet) goto Scene III
... some statements here
goto Scene II
Scene III:
... more statements here

is essentially equivalent to

while (Juliet <= Hamlet) {
   ... some statements here
}
... more statements here
chi
  • 14,564
  • 1
  • 30
  • 40