Timeline for Fewest (distinct) characters for Turing Completeness
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 17, 2020 at 9:04 | history | edited | CommunityBot | Commonmark migration | |
| Apr 13, 2017 at 12:39 | history | edited | CommunityBot | replaced http://codegolf.stackexchange.com/ with https://codegolf.stackexchange.com/ | |
| Feb 23, 2017 at 8:47 | history | edited | Laikoni | CC BY-SA 3.0 | added fix function to become turing complete |
| Feb 21, 2017 at 15:03 | comment | added | user62131 | @Laikoni: There's no way to write an infinite loop in simply typed lambda calculus unless you have some extra help from something like a fixed-point combinator (the Y combinator is the best known but not the only one that exists); every combinator that would help you write an infinite loop doesn't exist in the type system in question. You can certainly do a lot of interesting things with terminating programs, but that isn't enough for Turing completeness. | |
| Feb 21, 2017 at 15:01 | comment | added | user62131 | @PyRulez: If you have no lambdas and no other combinators, I don't think a fixed-point combinator like Y is enough by itself (although I'm very tired right now and there may well be something I'm missing). | |
| Feb 21, 2017 at 12:33 | comment | added | Christopher King | @ais523 how many combinators does typed Lambda Calculus need to be complete? I think you just need the y combinator, right? | |
| Feb 21, 2017 at 8:47 | comment | added | Laikoni | @ais523 The SKI combinators are just an example, using the given notation arbitrary lambda terms can be build, e.g. church numerals and functions on them. | |
| Feb 21, 2017 at 8:37 | comment | added | Laikoni | @PyRulez As per the default rules I assumed that functions are acceptable. | |
| Feb 21, 2017 at 2:34 | comment | added | user62131 | The simply typed SKI combinator calculus isn't Turing-complete; you need an untyped lambda calculus for that. Unfortunately, as your demonstrations mention, Haskell puts a typed interpretation on the code by default. | |
| Feb 21, 2017 at 0:38 | comment | added | Christopher King | Won't it technically be removed at compile time without main? | |
| Feb 21, 2017 at 0:18 | history | edited | user61980 | CC BY-SA 3.0 | Spelling |
| Feb 20, 2017 at 19:28 | history | edited | Laikoni | CC BY-SA 3.0 | added 290 characters in body |
| Feb 20, 2017 at 19:19 | history | answered | Laikoni | CC BY-SA 3.0 |