Show Posts
736
TI Z80 / Re: TCPS embedded/independent scripting language
« on: June 21, 2011, 05:24:09 am »
Let us assume that each instruction can be mapped to a finite set of integers from 0 to some number X. Let the number of possible states of the interpreter be similarly mapped some potentially infinite set of integers from 0 to m. Before continuing further, it must also be mentioned that any Turing complete language can store an infinite amount of data. Since TCPS has finite memory (due to the underlying hardware constraints), it is not truly Turing complete. However, it is common to ignore such constraints and assume that the language has access to an infinite amount of memory if it chooses to utilize it. I will assume that here as well. Also, the simplest way to prove TCPS Turing complete is just to recognize that since brainf*ck is Turing complete and Assembly can implement a brainf*ck interpreter while TCPS allows inline Assembly, TCPS is Turing complete by extension. However, the command list given does not have a command for arbitrary input [like brainf*ck's ',' command]*, TCPS cannot perfectly emulate brainf*ck. While this is really quite a significant oversight, excluding emulation of this command does not necessarily make TCPS Turing-incomplete (as a cursory examination of the properties of Rule 110 will demonstrate).
Now, in order for a language to be Turing-Complete, it must be able to emulate any possible Turing machine. In other words, there must be a 1-to-1 mapping of TCPS programs to Turing Machines. The data requirements of a Turing machine are 1) A Turing tape, which is essentially an infinitely large array of numbers, B) A number representing the memory location on the tape currently being accessed by the head, and C) a number representing the state of the machine. Let the memory space accessibly by the interpreter suffice as a representation of the tape. Let the memory location (PC) currently accessed by stored in some place either on the tape or internal to the interpreter while the state of the interpreter consists of the values of all other data contained within the program.
From the above requirements for Turing-completeness, it can be seen that any system which implements the following program is thus Turing-Complete:
While one could conceivably generating many other Turing-Complete programs, this is I think the most intuitive one. Since all Turing-Complete systems are Turing-Equivalent, any Turing-Complete system can implement that program and every non-Turing-Complete systems are missing one of the abilities. Therefore, a system is Turing-Complete if and only if the program can be implemented.
Label <string>:
Labels are primarily a human construct and need not actually appear in the tape. Assume Labels to refer to particular memory locations in a manner similar to pointers.
If {PC}=x Then:
This routine can be accomplished in much the same manner as in brainf*ck. Subtract 1 from{PC} x times and then use the '[' and ']' looping commands to test the conditional.
Change State to Qₓ :
Again, this can be accomplished in much the same way as brainf*ck. Use the '+' and '-' operators to change the value of {PC} and the '<' and '>' operators respectively to
access other memory locations (see the part on Goto for a description of the difficulties associated with this).
Change {PC} to Rₓ:
'+' or '-' will suffice.
Change PC to PCₓ ':
Precisely the same idea as “Change State to Qₓ “
Goto <Label>
Okay, I'll be honest; TCPS can't actually do an arbitrary Goto <Label>. Neither can Brainf*ck. To actually do so in either language is equivalent to solving the Halting Problem, which has been proven to be generally undecidable. This does not mean that TCPS isn't Turing-Complete though, as the provided example program can be rewritten such that the conditionals are located at one point on the tape and Goto <Label> is equivalent to a finite (and known!) number of '<' or '>' operators. I'll leave implementing as an exercise, as the general case is one of those things that makes babies cry and milk go sour.
End:
This is another primarily human construct that need not necessarily exist on the tape. It's essentially just the ']' command.
Halt:
This is the '!' command.
Since the program can indeed be implemented, TCPS is therefore Turing-Complete and this informal proof is thus concluded.
*The ability to input filenames, while technically "arbitrary input," just doesn't seem like a reasonable substitute since you'd basically have to write programs for each case of a computable problem. You could theoretically use this in a BF interpreter written in TCPS, but come on. Getkey is so simple that even BF has it >_>
PS: If you'd like my opinion, I don't think TCPS is really in the spirit of Brainf*ck, which was designed to be a Turing-Tarpit. Adding extra commands is kind of like putting more legs on a Kangaroo IMHO. It might make it easier for the Kangaroo to jump, but it's now it's a mutant Kangaroo. But it's your project, so good luck finishing it
EDIT: Sorry for the weird spacing. I typed this up in a word processor and the forum doesn't use the same typesetting.
Now, in order for a language to be Turing-Complete, it must be able to emulate any possible Turing machine. In other words, there must be a 1-to-1 mapping of TCPS programs to Turing Machines. The data requirements of a Turing machine are 1) A Turing tape, which is essentially an infinitely large array of numbers, B) A number representing the memory location on the tape currently being accessed by the head, and C) a number representing the state of the machine. Let the memory space accessibly by the interpreter suffice as a representation of the tape. Let the memory location (PC) currently accessed by stored in some place either on the tape or internal to the interpreter while the state of the interpreter consists of the values of all other data contained within the program.
From the above requirements for Turing-completeness, it can be seen that any system which implements the following program is thus Turing-Complete:
Code: [Select]
Label: Beginning
If {PC}=0 Then
Change State to Q₀
Change {PC} to R₀
Change PC to PC₀ '
Goto Beginning
End
If {PC}=1 Then
Change State to Q₁
Change {PC} to R₁
Change PC to PC₁'
Goto Beginning
End
…
If {PC}=[i]x[/i] Then
Change State to Qₓ
Change {PC} to Rₓ
Change PC to PCₓ '
Goto Beginning
End
If (State Or {PC}) = (Halting_Condition) Then
Halt
End
While one could conceivably generating many other Turing-Complete programs, this is I think the most intuitive one. Since all Turing-Complete systems are Turing-Equivalent, any Turing-Complete system can implement that program and every non-Turing-Complete systems are missing one of the abilities. Therefore, a system is Turing-Complete if and only if the program can be implemented.
Label <string>:
Labels are primarily a human construct and need not actually appear in the tape. Assume Labels to refer to particular memory locations in a manner similar to pointers.
If {PC}=x Then:
This routine can be accomplished in much the same manner as in brainf*ck. Subtract 1 from{PC} x times and then use the '[' and ']' looping commands to test the conditional.
Change State to Qₓ :
Again, this can be accomplished in much the same way as brainf*ck. Use the '+' and '-' operators to change the value of {PC} and the '<' and '>' operators respectively to
access other memory locations (see the part on Goto for a description of the difficulties associated with this).
Change {PC} to Rₓ:
'+' or '-' will suffice.
Change PC to PCₓ ':
Precisely the same idea as “Change State to Qₓ “
Goto <Label>
Okay, I'll be honest; TCPS can't actually do an arbitrary Goto <Label>. Neither can Brainf*ck. To actually do so in either language is equivalent to solving the Halting Problem, which has been proven to be generally undecidable. This does not mean that TCPS isn't Turing-Complete though, as the provided example program can be rewritten such that the conditionals are located at one point on the tape and Goto <Label> is equivalent to a finite (and known!) number of '<' or '>' operators. I'll leave implementing as an exercise, as the general case is one of those things that makes babies cry and milk go sour.
End:
This is another primarily human construct that need not necessarily exist on the tape. It's essentially just the ']' command.
Halt:
This is the '!' command.
Since the program can indeed be implemented, TCPS is therefore Turing-Complete and this informal proof is thus concluded.
*The ability to input filenames, while technically "arbitrary input," just doesn't seem like a reasonable substitute since you'd basically have to write programs for each case of a computable problem. You could theoretically use this in a BF interpreter written in TCPS, but come on. Getkey is so simple that even BF has it >_>
PS: If you'd like my opinion, I don't think TCPS is really in the spirit of Brainf*ck, which was designed to be a Turing-Tarpit. Adding extra commands is kind of like putting more legs on a Kangaroo IMHO. It might make it easier for the Kangaroo to jump, but it's now it's a mutant Kangaroo. But it's your project, so good luck finishing it
EDIT: Sorry for the weird spacing. I typed this up in a word processor and the forum doesn't use the same typesetting.
).