As a sort of sequel to my footnote about printf being Turing complete on @drummyfish’s Iceberg topic, here’s a list of things that are accidentally turing complete. (Incidentally, this list includes a lot of the Turing completeness examples from the iceburg.)
Fittingly, I wasn’t actually intending to make a topic about this, I just stumbled upon this accidentally and thought it would be worth sharing.
The one I’m most surprised about is Java’s generics being Turing complete. Unfortunately the proof is an academic paper I have no hope of understanding.
Pretty cool. Other things include rule 110 and Minesweeper. Apparently it’s not difficult to achive Turing completeness at all, quite the contrary, when there is infinite iteration/recursion possible, you’re dangerously close.
The HTML5 + CSS3 example is a rule 110 implementation, so it’s sort of implied but not explicitly stated.
No it isn’t, but it’s still amusing when things are accidentally turing complete because of the possibilities that arise.
Another thing that can be implemented to prove Turing completeness is lambda calculus*, which personally I find far more interesting because of its use as a basis for various functional programming languages.
It’s interesting that two of the ones listed, Little Big Planet and X86 MMU, give an implementation of Conway’s Game of Life as an example, since the Game of Life is itself Turing complete.
Yeah, also the “OOP” sigma calculus. General recursive functions and type 0 grammars are other Turing complete computational models you can use in proofs. Basically you can look at any computational class equally in terms of either grammars, automata or functions, depending on what suits you best – e.g. automata are language “acceptors” whereas grammars are language generators, you can pick whichever is more convenient for you.
It’s not just Turing complete vs. Turing incomplete, it gets much more interesting when you consider all other classes that you get when you start restricting and expanding the models (e.g. by determinism, adding stacks etc.). Going down this rabbit hole is pretty interesting but may also have an effect on your mental health, I’ve had my share of it in the school and think it’s about enough for the rest of my life. Sometimes some of the the non Turing complete languages are even more interesting – there’s this trivia that I always remember when looking back that a pushdown automaton cannot tell which words are of form a^n b^n c^n, but it can tell all which are not of that form (i.e. the language is not context-free but it’s inverse is). It’s like if you can’t recognize Chinese language but can 100% recognize everything that’s not Chinese, because that’s somehow much easier.
Yeah and then of course you have languages that are “above” Turing completeness like Perl xD That’s from the iceberg.
I’ve suddenly realised that as far as I’m aware there isn’t a GoL implementation for Pokitto. That definitely needs rectifying at some point.
I’ve struggled to find references to this. Most of what I can find is about the ‘for loop’ form of capital sigma used in maths.
I did manage to find this implementation (fortunately written in Haskell).
I have some thoughts about it, but I won’t go into them now since I doubt many people are particularly interested. (I don’t expect many people visit here for discussions about computer science theory.)
I’ve never had the fortune of learning any of this sort of thing in school or college. Everything I know about Turing completeness and most other ‘computer science’ topics (and every language except for VB and Java) I’ve learnt by reading online articles (or, more rarely, books).
By a^n do you mean "n copies of a" (typically denoted a{n} in many regex variants, such as grep) or something else?
The Life engine I wrote for the MicroView version and used with the Arduboy version is separate and fairly portible. If it were used for a Pokitto version, only a front end and rendering would be needed.
I was thinking about doing some portable GoL “engine” that would have features like very large worlds with tiny RAM usage by using a sparse array. Now I’m thinking about doing it as part of SAF.
I don’t have references either, I’ve just heard about it from some teacher. He showed us a few examples how it worked but I won’t be able to remember it, the definition of that language is probably buried in some obscure scientific papers.
Yes, it’s a math notation, you denote repetition of a string by a superscript, like raising numbers to powers. Here’s a related CS stack exchange question to that trivia.
The link I left mentioned its source, which I’ve since been able to verify. It’s from a 1998 book called “A Theory of Objects” by Martín Abadi and Luca Cardelli. Specifically chapter 6.2, page 60. (I found a table of contents.)