As far as I can tell, I do not think that Rook is the smallest Turing tarpit. Iota has a simpler definition than this. (It contains of just applications of iota function.) Please specify what you mean by saying "made to be the smallest Turing tarpit ever". --
A (talk) 15:09, 21 June 2019 (UTC)
Hmm, I do not think that this is Turing complete, as it can only provide data deleting when the tape is filled with values (that is impossible if the tape is unbounded). "The F acts as the EJECT command when the tape is completely filled with F's and T's." A Turing complete Computational model requires infinite memory. --
A (talk) 15:16, 21 June 2019 (UTC)
In Response to User: A
What I mean by "made to be the smallest Turing tarpit ever", is exactly as it sounds. I believe it could be considered a popular problem where many have tried to create the smallest turing tarpit (For example, Brainfuck). When I say, "made to be the smallest Turing tarpit ever", it's my attempt on making the smallest Turing tarpit. Also, your statement, "As far as I can tell, I do not think that Rook is the smallest Turing tarpit. Iota has a simpler definition than this. (It contains of just applications of iota function", is false. Iota, while it only uses 2 symbols (the minimum symbols needed for a turing-complete language), and 2 instructions, it's not smaller than Rook simply due to its use of combinatory logic (Highly evident once you look at the page). Rook just needs a list of 126 T's or F's for a complete program. Combinatory logic has a very simple, yet (roughly) more complex than Rook's syntax. As for the issue on Turing Completeness, this is a valid concern that I'll correct. Areallycoolusername (talk) 16:07, 23 June 2019 (UTC)Areallycoolusername
Please specify again
This specification is too unclear in the specifications of double F's. For example, in this program:
Furthermore, can you specify what T and F will do when you made the tape unbounded? You have only specified that the T command will not go to the last cell; but what will it do? You have also specified that the FF commands halts the program; what does the F command do here? The F command will definitely not apply to this new document.--
A (talk) 23:53, 25 June 2019 (UTC)
The parser would treat the halt command as 2 F's, and would stop the program when detected. There is no need for a another mechanism, since anymore than 1 T in a row, and anymore than 2 F's in a row will be treated as a single T and single F would (Declaring the cell true or false).
I have already specified in the "Specifics" section of the page, that the two commands will act exactly the same as they did in the original idea, with some exceptions. These being:
a)The F command won't act as EJECT would when the tape is full, since the tape is now unbounded and the tape would never be full.
b)The first command, which can either an F or T, will not go the last cell of the tape since the tape is now infinite. It will instead to the the first cell which now represents the 32nd character in the ASCII table, instead of the 126th character.
c)Since the tape is unbounded, the interpreter can no longer stop at prompting the user for 95 T's and F's. Instead, it would continue prompting the user for another set of 95 T's and F's. This is why the halt command, FF, was implemented. It would stop the interpreter from prompting the user, print the cells corresponding ASCII characters which held T's, and ends the program.
(Unfortunately) bounded memory support
I see(I previously thought that Rook only supports writing programs as a one-liner). Unfortunately, Rook still only supports bounded memory. As in the documentation, it supports indexing the last item in the memory. A real Turing-complete language can only index the last item in a cell-based memory in infinite time. If a language can index it in a finite amount of time, then the cells between the beginning cell and the last cell are obviously bounded. As such, it only supports bounded memory, and is not Turing-complete. (It is impossible to simulate data with infinite memory, as the user cannot type in that much memory in a finite amount of time, and if the user kept typing it, then the interpreting step will never be reached.) --
A (talk) 04:18, 27 June 2019 (UTC)
- If Rook having bounded memory is the case, do you have any suggestions as to how to make Rook Turing complete? As for your suggestion that the double F should be replaced by the end of file, I'll try to implement that. I was having trouble trying to implement the double F into the interpreter, so this might make it easier to write, and lower the complexity of the language.
Could You Specify
Could you specify what you mean by, "Just make sure that the commands operate on the first cell, as this does not affect the length of the memory" ? Areallycoolusername (talk) 21:11, 29 June 2019 (UTC)Areallycoolusername
- Never mind, I don't know how to explain it. --U SerA 13:49, 28 June 2019 (UTC)