Talk:Shakespeare
Shakespeare Turing Complete?
This is a Draft Proof I made that Shakespeare is Turing Complete by converting BF code to Shakespeare (hereby denoted as S).
Most proofs, If i remember correctly translate all of the BF commands to its target language. I shall try to do the same here!
BF: '>' Move the pointer to the right
S: Since each charater has a stack, the memory array can be emulated using two stacks. Call them Romeo and Juliet. Juliet always has the value that we're pointing to. Juliet is to the right of Romeo. Therefore: We give Juliet's current value & push it into Romeo's Stack. Of course the stack is finite, if we know that Juliet's stack is now empty, we assign the new value of zero to Juliet. We may need a way to keep track of the stacks in order to know if any one of them is empty. Is so, this might negate turing completeness.
I didn't find anything in the code regarding wether or not S can provide a means for checking that a stack is empty. Therefore I propose this workaround:
Assign two control values: call them A and B. They can be any reasonable number that Shakespeare can handle (for example 255 and 250, respectively). We pop A into each of the empty stacks and this is our marker for empty stacks. If we need to use the value A as data, we first push B and then A. Likewise, if we need to use B as part of the data, we push B twice (this sounds like a Nintendo Game). When we pop values from one stack into another, we interpret B as a control value and the real data value will be the one being popped after it.
Note: If the BF implementation only uses 0-255 as its values, and Shakespeare can use more (such as 0-65535) then we can let A>255 and not worry about B.
BF: '<' Move the pointer to the left
S: Same as before. Only now we're giving Rome's current value to Juliet. Everything else mentioned stands.
BF: '+' Increment the memory cell under the pointer
S: This one is easy. We increment Juliet's current value by one. We wrap the values as necessary.
BF: '-' Decrement the memory cell under the pointer
S: Same thing. Instead, we decrement Juliet's current value by one.
BF: '.' Output the character signified by the cell at the pointer
S: Juliet: Speak your mind! Note: We must also compensate for end-of-stack markers if necessary.
BF: ',' Input a character and store it in the cell at the pointer
S: Juliet: Open your mind!
BF: '[' Jump past the matching ']' ] if the cell under the pointer is 0
S: This one's a little tricky, but still doable. Since BF has no "line numbers" while S does, this part needs to be done while we have a complete understanding of our code. We must keep track of all the scenes (we assume there is only one act), and increment a scene number whenever we encounter one of these. The same is done for ]. We then use that information to jump to the correct scene if Juliet has the value of zero.
Note: I am not sure if this solution for this instruction would count as part of proving Turing-completeness. S might have only a finite number of scenes available for use... especially since the scenes are written in Roman Numerals, which can represent only a finite set of numbers (as far as I know). If Roman Numerals can represent (or can be made to represent) an infinite set of numbers then we're ok. However, a more sophisticated solution may be in order.
BF: '[' Jump back to the matching ']'
S: The principle is the same as above, except that there is no comparison being done, the jump is unconditional.
This is a very rough sketch I made several days ago, and is my first attempt and proving Turing-Completeness. Any comments/suggestions would be greatly appreciated! --Stux 15:02, 31 Oct 2005 (GMT)
- Does Shakespeare require these Roman numerals to be actual, valid Roman numerals, or could you have numbers like IIII, IIIII, IIIIII, etc? --Ihope127 16:53, 31 Oct 2005 (GMT)
- The Roman Numerals problem is actually not a problem, as BF interpreters exist written in BF. Shakespeare has enough scenes available to represent all the brackets necessary in a simple interpreter. This method may prove useful for getting around similar constraints in other programming languages. -- User:ais523 17:18, 02 May 2006 (GMT)
I've made a Python3 program that converts BF programs to SPL programs (however, the method I use for retrieving items from the "tape" is inefficient; I might use something similar to the method above if I were to rewrite it). --JWinslow23 (talk) 14:05, 6 September 2018 (UTC)