Timeline for Are there minimum criteria for a programming language being Turing complete?
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 21, 2024 at 0:02 | comment | added | Mark Rosenblitt-Janssen | I believe you can do that if you use the "two's complement" method to simulate a -1 in binary logic. But you may have a point, increment may not work in two's complement. | |
| Jul 2, 2024 at 22:09 | comment | added | Raphael | @theDoctor Not if you don't have _ - 1, I don't think; see the comments above. If you can prove otherwise, please add an answer! | |
| Jul 2, 2024 at 17:52 | comment | added | Mark Rosenblitt-Janssen | 5 is unnecessary if you have 6. | |
| May 7, 2023 at 3:48 | comment | added | Kevin | @Raphael: Not to intrude on a long-forgotten thread, but to my mind, "the language must have a decrement" feels like a much more natural requirement than "the language must be able to express two different kinds of loops, one of which coincidentally causes a variable to be decremented." But that's just my personal taste. | |
| Feb 3, 2015 at 12:41 | history | edited | Raphael | CC BY-SA 3.0 | Removes fallacious assertion; we need `for`. |
| Feb 3, 2015 at 12:39 | comment | added | Raphael | @MSalters I think you are right; for the simulation I seem to have had in mind, we need _ - 1 and I can not think of a way to implement that without for. Thanks for catching that! (What is "better" -- including _ - 1 or for? Hmm.) | |
| Feb 3, 2015 at 11:03 | comment | added | MSalters | I think it's obvious that you cannot drop the 5th rule in the language. Since the while loop in 6 compares to the constant zero, variables can only be incremented by rule 2 and there are no negative constants to start from (rule 1), the while loop in 6 is either not entered (x=0) or it's infinite (x>0, and loop body cannot decrease it). | |
| Apr 3, 2012 at 5:48 | history | edited | Raphael | CC BY-SA 3.0 | added 6 characters in body |
| Apr 2, 2012 at 23:02 | vote | accept | Khanzor | ||
| Apr 2, 2012 at 17:50 | history | edited | Raphael | CC BY-SA 3.0 | added 73 characters in body |
| Apr 2, 2012 at 16:57 | history | answered | Raphael | CC BY-SA 3.0 |