Timeline for Smallest subset of characters required for Turing Completeness
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 24, 2022 at 17:18 | comment | added | DLosc | My guess is that there might be a way to be Turing-complete without + and =, but ~ is crucial since it's the only way to add bits to the playfield. IIRC, infinite growth of data is a necessary condition for Turing-completeness. | |
| May 20, 2022 at 17:07 | comment | added | des54321 | I'm not 100% sure about +, but I am pretty sure that ~ doesnt allow you to do much in the way of conditionals. It might be possible to make something really janky with + that lets you simulate the behavior of = though | |
| May 20, 2022 at 7:27 | comment | added | Aiden Chow | @des54321 So you saying that I can take out ~ and + and leave it as =? | |
| May 20, 2022 at 4:27 | comment | added | des54321 | I'm pretty you dont actually need the dupneg in there, because without being able to tell the difference between a 1 and a 0 with either + or =, you cant make any kind of conditional. There might even be a case that could be made for taking out +, as I dont think theres any way to emulate that behavior with `+/` | |
| May 20, 2022 at 3:31 | history | answered | Aiden Chow | CC BY-SA 4.0 |