2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Have you seen: cs.stackexchange.com/questions/2832/… ? In given language you declare number of stacks to use, two will suffice. There are conditionals and goto instructions, so there are loops. $\endgroup$ – Evil Feb 23 '19 at 4:11
  • 1
    $\begingroup$ Loops in Shakespeare can be created with gotos. $\endgroup$ – Discrete lizard Feb 23 '19 at 9:33
4
$\begingroup$

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.