Timeline for Fewest (distinct) characters for Turing Completeness
Current License: CC BY-SA 3.0
140 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 10 at 18:20 | answer | added | l4m2 | timeline score: 0 | |
| Oct 4 at 6:53 | answer | added | The Empty String Photographer | timeline score: 1 | |
| Sep 13 at 3:22 | answer | added | Andrew Bayly | timeline score: 5 | |
| May 8 at 12:06 | answer | added | None1 | timeline score: 0 | |
| May 8 at 11:54 | answer | added | None1 | timeline score: 0 | |
| Nov 23, 2023 at 21:08 | answer | added | ceilingcat | timeline score: 2 | |
| Nov 19, 2023 at 4:47 | answer | added | Yousername | timeline score: 2 | |
| Sep 13, 2023 at 10:50 | answer | added | emanresu A | timeline score: 5 | |
| Jul 22, 2023 at 15:00 | answer | added | The Empty String Photographer | timeline score: 0 | |
| S Mar 30, 2023 at 9:31 | history | bounty ended | pxeger | ||
| S Mar 30, 2023 at 9:31 | history | notice removed | pxeger | ||
| Mar 25, 2023 at 20:10 | answer | added | Joao-3 | timeline score: 0 | |
| S Mar 25, 2023 at 13:42 | history | bounty started | pxeger | ||
| S Mar 25, 2023 at 13:42 | history | notice added | pxeger | Reward existing answer | |
| Jan 20, 2023 at 18:56 | answer | added | l4m2 | timeline score: 1 | |
| Jan 20, 2023 at 9:34 | answer | added | arxenix | timeline score: 5 | |
| Aug 30, 2022 at 20:08 | answer | added | Seggan | timeline score: 0 | |
| Aug 14, 2022 at 3:16 | answer | added | Aiden Chow | timeline score: 3 | |
| Jul 30, 2022 at 2:49 | answer | added | kzh | timeline score: 24 | |
| May 24, 2022 at 19:48 | answer | added | prosfilaes | timeline score: 1 | |
| May 23, 2022 at 8:45 | answer | added | Olivier Grégoire | timeline score: 2 | |
| Apr 18, 2022 at 2:59 | answer | added | Ohentis | timeline score: 4 | |
| Apr 10, 2022 at 14:31 | answer | added | Yousername | timeline score: 2 | |
| Apr 1, 2022 at 22:33 | answer | added | Yousername | timeline score: 6 | |
| Mar 31, 2022 at 21:56 | comment | added | Yousername | I assume Piet (0 characters) is not a valid language to use for this challenge? | |
| Feb 17, 2022 at 7:20 | answer | added | xiver77 | timeline score: 3 | |
| Nov 22, 2021 at 18:24 | answer | added | Deadbeef | timeline score: 5 | |
| Nov 22, 2021 at 11:48 | answer | added | CreaZyp154 | timeline score: 1 | |
| Apr 15, 2021 at 3:02 | answer | added | PkmnQ | timeline score: 2 | |
| Mar 17, 2021 at 4:30 | answer | added | user100411 | timeline score: 1 | |
| Feb 20, 2021 at 0:08 | answer | added | Makonede | timeline score: 1 | |
| Feb 13, 2021 at 2:03 | answer | added | hakr14 | timeline score: 1 | |
| Feb 7, 2021 at 14:41 | answer | added | EasyasPi | timeline score: 4 | |
| Feb 3, 2021 at 16:43 | answer | added | pxeger | timeline score: 7 | |
| Sep 17, 2020 at 15:13 | answer | added | 2014MELO03 | timeline score: 6 | |
| Sep 9, 2020 at 8:00 | answer | added | Kevin Cruijssen | timeline score: 5 | |
| Sep 9, 2020 at 6:17 | answer | added | bb94 | timeline score: 3 | |
| Aug 31, 2020 at 8:05 | answer | added | Bubbler | timeline score: 7 | |
| Jun 17, 2020 at 9:04 | history | edited | CommunityBot |
Commonmark migration
|
|
| Mar 27, 2020 at 4:43 | answer | added | Bubbler | timeline score: 1 | |
| Mar 15, 2020 at 0:46 | answer | added | cardboard_box | timeline score: 5 | |
| Mar 13, 2020 at 17:34 | answer | added | S.S. Anne | timeline score: 3 | |
| Sep 15, 2019 at 3:52 | answer | added | ais523 | timeline score: 26 | |
| Sep 14, 2019 at 10:13 | answer | added | user85052 | timeline score: 1 | |
| Mar 25, 2019 at 15:49 | comment | added | univalence | the day of combinatory logic | |
| Mar 25, 2019 at 9:35 | answer | added | Jo King♦ | timeline score: 1 | |
| Feb 13, 2019 at 1:35 | answer | added | MilkyWay90 | timeline score: 1 | |
| Feb 8, 2019 at 1:20 | comment | added | Ørjan Johansen | @CalculatorFeline See also Brainfuck minus - on the esolang wiki. | |
| Jun 18, 2017 at 17:48 | comment | added | CalculatorFeline | Note: The Brainfuck answer does not actually require wrapping cells (look up Wang B machines) | |
| S Jun 6, 2017 at 16:57 | history | bounty ended | CommunityBot | ||
| S Jun 6, 2017 at 16:57 | history | notice removed | user62131 | ||
| Jun 6, 2017 at 13:19 | comment | added | Dennis | Unless I misunderstood your challenge, the score of a submission is the amount of unique characters, lower being better. That makes Unary the formal winner, as boring as the answer is. You can either accept the answer or accept none of them. What you cannot do is accept an arbitrary answer, as it violates the meta consensus and basically means your challenge no longer has an objective winning criterion (thus making it off topic). | |
| Jun 6, 2017 at 10:42 | comment | added | Julian Lachniet | @Dennis Since their is no "winner," I accepted the one with the most votes. | |
| Jun 6, 2017 at 3:52 | comment | added | Dennis | @JulianLachniet The accepted answer is the answer that wins the challenge. If you must, you can simply not accept any answer at all, but you shouldn't accept an arbitrary one. | |
| Jun 6, 2017 at 0:49 | vote | accept | Julian Lachniet | ||
| Jun 6, 2017 at 13:25 | |||||
| Jun 5, 2017 at 23:44 | answer | added | MD XF | timeline score: 0 | |
| S Jun 2, 2017 at 13:31 | history | bounty started | CommunityBot | ||
| S Jun 2, 2017 at 13:31 | history | notice added | user62131 | Reward existing answer | |
| Jun 1, 2017 at 18:44 | answer | added | Grimmy | timeline score: 47 | |
| Apr 15, 2017 at 1:45 | vote | accept | Julian Lachniet | ||
| Jun 6, 2017 at 0:49 | |||||
| Feb 26, 2017 at 21:15 | answer | added | Joshua | timeline score: -3 | |
| Feb 25, 2017 at 13:40 | answer | added | user63956 | timeline score: 12 | |
| Feb 25, 2017 at 9:20 | answer | added | Orion | timeline score: 4 | |
| Feb 25, 2017 at 7:38 | answer | added | DLosc | timeline score: 4 | |
| Feb 25, 2017 at 3:52 | comment | added | Julian Lachniet | @Nathaniel Whichever makes most sense in context. | |
| Feb 25, 2017 at 1:03 | comment | added | N. Virgo | Is it enough to specify a Turing-complete function, or does it have to be a complete program? | |
| S Feb 24, 2017 at 22:29 | history | bounty ended | Julian Lachniet | ||
| S Feb 24, 2017 at 22:29 | history | notice removed | Julian Lachniet | ||
| Feb 24, 2017 at 22:29 | vote | accept | Julian Lachniet | ||
| Feb 24, 2017 at 22:29 | |||||
| Feb 24, 2017 at 18:03 | answer | added | sporkl | timeline score: 3 | |
| Feb 24, 2017 at 15:38 | answer | added | mmachenry | timeline score: 10 | |
| Feb 24, 2017 at 2:30 | comment | added | Cort Ammon |
@ais523 Yeah, it's a bit awkward, but I think the only real question would be whether you need a constructive proof that the language works or not. I'm not sure if you could find a way to construct CHAR_BIT, though you could prove that it was a natural number and thus fits into a single char compile-time constant.
|
|
| Feb 24, 2017 at 1:18 | comment | added | user62131 |
@CortAmmon: I think you're confusing C with C++. In C, there's a potential issue with CHAR_BIT, which is a compile-time constant, but I guess it could be an infinitely large integer (which fits into one infinitely large byte)?
|
|
| Feb 23, 2017 at 21:38 | comment | added | Cort Ammon |
@ais523 C can be Turing-complete without file systems, but you have to use some pathological definitions of a "byte" to do so. You can play the power-set game to declare the byte to have a finite length, but the number of possible values of that byte is countably infinite. It does get a bit hard to define std::numeric_limits<int>::max() that way however. You have to play some games there too (like having max() never complete).
|
|
| Feb 23, 2017 at 20:14 | answer | added | 12Me21 | timeline score: 1 | |
| S Feb 23, 2017 at 16:52 | history | bounty started | Julian Lachniet | ||
| S Feb 23, 2017 at 16:52 | history | notice added | Julian Lachniet | Reward existing answer | |
| Feb 23, 2017 at 13:52 | history | edited | Julian Lachniet | CC BY-SA 3.0 |
added 72 characters in body
|
| Feb 23, 2017 at 1:16 | answer | added | user62131 | timeline score: 109 | |
| Feb 22, 2017 at 21:23 | answer | added | DLosc | timeline score: 6 | |
| Feb 22, 2017 at 4:51 | answer | added | user18932 | timeline score: 5 | |
| Feb 22, 2017 at 3:10 | answer | added | Bergi | timeline score: 3 | |
| Feb 21, 2017 at 21:58 | answer | added | corvus_192 | timeline score: 4 | |
| Feb 21, 2017 at 21:45 | answer | added | Tygrak | timeline score: 3 | |
| Feb 21, 2017 at 21:40 | answer | added | RenderSettings | timeline score: 3 | |
| Feb 21, 2017 at 21:38 | answer | added | SuperJedi224 | timeline score: 0 | |
| Feb 21, 2017 at 21:06 | answer | added | ceilingcat | timeline score: 31 | |
| Feb 21, 2017 at 19:49 | answer | added | AdmBorkBork | timeline score: 4 | |
| Feb 21, 2017 at 18:48 | answer | added | marinus | timeline score: 4 | |
| Feb 21, 2017 at 15:40 | answer | added | Poke | timeline score: 22 | |
| Feb 21, 2017 at 14:17 | comment | added | Darren Ringer | To me, the top comment of "Unary" was actually by far the most interesting thing to come of this question. There's a discussion somewhere about implementing a quine in brainfuck, converting the symbols to binary, then encoding the resulting number in unary. The number was something like 5*10^10000. | |
| Feb 21, 2017 at 13:03 | answer | added | Martin Ender | timeline score: 35 | |
| Feb 21, 2017 at 12:19 | answer | added | G B | timeline score: 9 | |
| Feb 21, 2017 at 12:18 | answer | added | Sp3000 | timeline score: 18 | |
| Feb 21, 2017 at 8:45 | answer | added | algorithmshark | timeline score: 3 | |
| Feb 21, 2017 at 6:00 | answer | added | user62131 | timeline score: 12 | |
| Feb 21, 2017 at 5:06 | answer | added | poi830 | timeline score: 15 | |
| Feb 21, 2017 at 4:58 | answer | added | user62131 | timeline score: 12 | |
| Feb 21, 2017 at 4:35 | answer | added | xsot | timeline score: 52 | |
| Feb 21, 2017 at 3:46 | answer | added | user62131 | timeline score: 10 | |
| Feb 21, 2017 at 2:54 | answer | added | user62131 | timeline score: 15 | |
| Feb 21, 2017 at 2:32 | answer | added | Devin Lehmacher | timeline score: 9 | |
| Feb 21, 2017 at 2:00 | answer | added | Conor O'Brien | timeline score: 5 | |
| Feb 20, 2017 at 23:59 | history | edited | Julian Lachniet | CC BY-SA 3.0 |
added 248 characters in body
|
| Feb 20, 2017 at 23:35 | review | Close votes | |||
| Feb 21, 2017 at 0:37 | |||||
| Feb 20, 2017 at 23:19 | comment | added | user62131 | @JulianLachniet: C probably isn't Turing-complete (although it depends on the implementation; it's possible to implement the file API in such a way that C becomes Turing-complete, but most implementations don't actually implement it like that). Thus, it isn't qualified for this challenge. | |
| Feb 20, 2017 at 22:14 | history | tweeted | twitter.com/StackCodeGolf/status/833802014886916098 | ||
| Feb 20, 2017 at 22:12 | answer | added | Blue | timeline score: 6 | |
| Feb 20, 2017 at 21:48 | comment | added | Paŭlo Ebermann | @rugdealer the idea is that you can implement any computable function from integers to integers (or strings to strings) in this subset of characters. | |
| Feb 20, 2017 at 21:36 | comment | added | Dennis | @Pavel Not interesting or clever may mean that it shouldn't get upvoted, but certainly not that it shouldn't get posted. | |
| Feb 20, 2017 at 21:15 | comment | added | kockburn | I'm confused as to what turing complete means, read a couple posts but it's very vague and the examples are quite vague as well. Anyone care on giving a very simple explanation? thanks (: | |
| Feb 20, 2017 at 20:46 | answer | added | nimi | timeline score: 97 | |
| Feb 20, 2017 at 19:27 | history | edited | xnor | CC BY-SA 3.0 |
Unique sounded like each character could only be used once.
|
| Feb 20, 2017 at 19:25 | history | edited | DJMcMayhem | CC BY-SA 3.0 |
Added tag, inlined link
|
| Feb 20, 2017 at 19:19 | answer | added | Laikoni | timeline score: 20 | |
| Feb 20, 2017 at 18:47 | answer | added | Martin Ender | timeline score: 21 | |
| Feb 20, 2017 at 18:39 | answer | added | mbomb007 | timeline score: 8 | |
| Feb 20, 2017 at 18:12 | answer | added | mbomb007 | timeline score: 26 | |
| Feb 20, 2017 at 18:00 | answer | added | James Holderness | timeline score: 11 | |
| Feb 20, 2017 at 17:29 | answer | added | Doorknob | timeline score: 45 | |
| Feb 20, 2017 at 17:20 | comment | added | Pavel | Please don't post solutions in esolangs where the solution is every valid character in the language. It's not intresting or clever. | |
| Feb 20, 2017 at 17:13 | answer | added | Martin Ender | timeline score: 21 | |
| Feb 20, 2017 at 16:44 | answer | added | user63187 | timeline score: 2 | |
| Feb 20, 2017 at 16:27 | answer | added | NoOneIsHere | timeline score: 9 | |
| Feb 20, 2017 at 16:16 | comment | added | Martin Ender | Related. (The challenges are very similar, but that one requires write an actual translator from an arbitrary program of the given language into a program using only the reduced character set, which can be a lot more difficult than simply proving that the reduced character set is Turing-complete. In fact it's possible to find Turing-complete subsets that cannot represent every program of the host language.) | |
| Feb 20, 2017 at 15:58 | comment | added | Martin Ender | @Fatalize I would expect answers to include at least a sketched proof which could be either a reduction from a known-to-be-TC language or implementation of a known-to-be-TC language with the reduced character set. | |
| Feb 20, 2017 at 15:57 | answer | added | Business Cat | timeline score: 21 | |
| Feb 20, 2017 at 15:50 | comment | added | Julian Lachniet | @Fatalize One way to check if it's Turing complete is to emulate Brainfuck, which is very simple. | |
| Feb 20, 2017 at 15:50 | history | edited | JungHwan Min | CC BY-SA 3.0 |
Please no mobile links
|
| Feb 20, 2017 at 15:44 | comment | added | Fatalize | I am pretty sure checking that an answer is valid in most languages will be difficult (excluding turing tarpits) | |
| Feb 20, 2017 at 15:42 | comment | added | Dennis | @MartinEnder Point taken. Might as well post the answer before someone else does then. | |
| Feb 20, 2017 at 15:41 | comment | added | Julian Lachniet | @MartinEnder I'd be especially interested to see answers in languages like Java or C. | |
| Feb 20, 2017 at 15:41 | answer | added | Dennis | timeline score: 69 | |
| Feb 20, 2017 at 15:39 | history | edited | Wheat Wizard♦ | CC BY-SA 3.0 |
wrapping environment (at least to me) implies a wrapping tape.
|
| Feb 20, 2017 at 15:38 | answer | added | Wheat Wizard♦ | timeline score: 19 | |
| Feb 20, 2017 at 15:35 | comment | added | Martin Ender | @Dennis It's not that different from Jelly or 05AB1E having a built-in for an interesting number theory problem. This challenge still seems like an interesting and non-trivial optimisation problem in any language that wasn't designed to be a tarpit. | |
| Feb 20, 2017 at 15:29 | history | edited | Julian Lachniet | CC BY-SA 3.0 |
deleted 2 characters in body
|
| Feb 20, 2017 at 15:24 | comment | added | Dennis | Unary, 1 character. sighs | |
| Feb 20, 2017 at 15:21 | history | edited | Julian Lachniet | CC BY-SA 3.0 |
edited body
|
| Feb 20, 2017 at 15:18 | history | asked | Julian Lachniet | CC BY-SA 3.0 |