On Magic The Gathering being Turing-complete, this is an interesting quote:
> Our result is also highly unusual in that all moves of both players are forced in the construction. This shows that even recognising who will win a game in which neither player has a non-trivial decision to make for the rest of the game is undecidable.
At first I thought this was pretty mind-blowing for a game, but actually this is directly comparable with a Turing machine; each step is forced, mechanical and very easy to derive, and yet, the overall behaviour is generally undecidable.
For anyone curious about the details of building a Turing machine in MtG, Because Science did a thorough breakdown and demonstration, using actual cards: https://youtu.be/pdmODVYPDLA
While rather more dense, I find Gwern's article/list[1] a bit more extensive (although missing a few from this list), while also having some interesting commentary on security implications.
I'm still not sure if Python Pickles, without the GLOBAL opcode to call into Python, are Turing complete.
Python pickle files are a sequence of op-codes that run on the pickle VM. By default the VM allows calls to arbitrary Python functions. I'm still puzzling whether Python pickles without access to Python globals (e.g. using https://docs.python.org/3/library/pickle.html#restricting-gl...) are Turing complete. I don't think so, because the pickle VM has no branching or looping, but it does have a stack and my understanding of automata theory is not great.
A machine that has a stack and runs a series of instructions in sequence, no looping or branching, is a pushdown automaton. That's significantly weaker than Turing complete.
(A pushdown automaton can do branching if it wants, but the lack of looping / going left is critical.)
This list is careful to mention that the PowerPoint machine requires the user to perform an action for each step, but neglects to make the same disclaimer for the HTML5 + CSS3 machine.
It's pretty hard to make something that is not turing-complete. I've always wondered if it wouldn't be beneficial to have a turing-incomplete language given that Rice's theorem then doesn't necessarily hold and thus very powerful semantic analysis might be possible. But the language is then probably not practical due to limited expressiveness.
This is kinda part of the promise of regular expressions, context-free grammars, relational algebra, map-reduce and other stream/pipeline-based programming models, and maybe to some extent P-complete things like convex optimizers and programming models based on horn clauses like datalog.
Each of these things aims to allow the user to specify a task in a restricted model of computation. In turn, it tends to be possible for the engineer writing the solver to build an engine capable of very radical transformations, optimizations, and analyses, that generally can't be matched by compilers and interpreters for Turing-complete programming languages.
If you have a VM that processes opcodes and has no way of (a) adding opcodes to the end or (b) moving backwards in the stream, it won't be Turing complete.
I've used a scripting system for a server that was intentionally written this way to bound the harm a misbehaving script could have on the server.
The simplest way to make something not Turing-complete is to put a bound on the resources it can use. Like giving it limited time and/or memory.
So you can have a practical, useful, non-Turing-complete language by forcing every function to have a limit on the number of steps it can take. It can be implicit if you want. In practice, most embedded scripting systems use this route, which is why you don't really need a separate language just for non-Turing-completeness.
This might get you away from the literal statement of Rice's theorem, but we tend to ask questions about our programs' behaviour across all possible inputs, and these questions tend to remain impossible to solve in general.
For example, finding out whether a time-bounded Turing machine outputs 0 all inputs is still undecidable. (coRE-complete, in fact. That's better in some sense than the Pi_2-completeness of the same problem for Turing machines without the time bound, but since neither admits a solution in the form of a computer program, a lot of people would consider the difference an academic curiosity only.)
Call the time bound c|x|^k, where x is the input and c and k are constants.
I see what point you're making, and I agree that you get yourself a nice, merely coNP-complete problem if you're willing to cut off the space of inputs at a point by enforcing a constant time bound or whatever. More than anything, this kind of argument makes me shudder at just how hard the very worst stuff in NP must be.
When people talk about "limited time and/or memory" for a runtime they're almost certainly talking about something constant, or a small polynomial of the input size.
But yes, it should reduce to NP territory. If you actually had a nondeterministic CPU, then for most use cases you could fully evaluate these machines in seconds.
> limited time [to] a small polynomial of the input size.
This is backwards; I meant that if you have any time bound whatsoever, the number of inputs you can inspect is limited to (a architecture-specific finite multiple of) the number of operations you can execute (because inspecting a input is such a operation).
If the time bound is being put in place in the hopes of being able to automatically analyze the behaviour of the code, then no.
I singled out "outputting 0" on every input because it's among the simplest possible specs you could try try to check with the kind of "very powerful semantic analysis" tool the top-level post was hoping for. In practice you probably want to check a more complex spec -- you want your code to solve a specific problem on whatever input it receives -- but if the "always output 0" spec is impossible to automatically check, then what hope do more relevant specs have?
Agreed. It's still just a hypothesis that interesting computing is equivalent to a turing machine and I don't buy it. For basically every program I've built, I could (hypothetically, bugs aside) either prove that it terminates, or it's a program like (forever do "something i can prove terminates"). The space of programs that we actually use seems kinda small. Designing a computing model that only covers what's useful while also making it convenient appears to be a long standing open problem. I'm sooooo curious to see things happen there.
This is the problem. Interesting computing is some impossibly complex (undecidable, in fact) subset of all computing, that you try to get inside of via the practice of software engineering. Turing's theory of computation provides reasoning tools which allow us to bring rigor to the idea that building correct software that does useful things is generally difficult.
> Designing a computing model that only covers what's useful while also making it convenient appears to be a long standing open problem.
Per the above point, depending on how you characterize this goal, it's probably impossible to accomplish.
>Interesting computing is some impossibly complex (undecidable, in fact) subset of all computing...
I totally disagree here. Or at least I totally disagree that it's a resolved question. All of those nasty problems that face some interesting programs don't face programs we actually write. For example, there is a subset of all turing complete programs that halt. The boundary of that subset isn't decidable, but when I'm writing a program that needs to halt, I write a program I know will halt (why are you pushing to prod if you don't know this program will halt?). Expending a ton of proof effort, I could prove that it halts. So I think the stuff we actually build in practical software is really far from the boundary of the nasty stuff.
Suppose I had a programming language that had a termination checker and only allowed programs it can prove will terminate. We know that the termination checker will have to return yes, no, and who knows. It can't just say yes and no without being wrong sometimes, because it's an undecideable problem. Maybe there's some termination checker that can correctly say yes to all the programs we really care about. Since I could prove that my programs terminate, this checker must exist. A language that only allows these programs must not be turing complete.
So there must be some non turing-complete languages that can express all the programs I would push to prod at work. Maybe some of those languages are even worth using.
Nope. I'm going to argue this every time I see it. It only demonstrates basic arithmetic. When an external actor has to come along and take each iteration's output and manually do things with it, you don't have Turing completeness.
That is clearly a demonstration of Turing completeness, but it's a demonstration of Turing completeness of HTML5 + CSS3 + copying from output back to input (the same as eg string rewriting systems) and that could stand to be stated more clearly.
Technically yes, but only when it's paired with the understanding that arithmetic plus copying the output back to input is Turing complete. HTML5+CSS is only supplying the arithmetic half of the equation.
I agree, I also think there is some weirdness going on with the 'we can presume it has infinite memory'. There seems to be many assumptions of different strength all waved with that same phrase, depending on the system in question.
Without that presumption how could anything ever be considered Turing complete?
If you're simulating something with infinite memory you get to pretend you have infinite memory. Feasibility has already been suspended.
Edit: ok I get it. Still, GP observation is hardly at that level from my (limited) perspective. Not being able to advance by itself means it's not a standalone system - otoh external actor is obviously implicit for many other examples as well. I suppose they (and me) are taking the word machine too literally.
But "pens are Turing-complete" seems a bit, well, diluted.
Turing Complete is not a very high bar. Add a second stack to a pushdown automata and its Turing Complete. Add two counters to a NFA and it’s Turing Complete. I am not sure if folks know what this means.
Yes. Judging from the HN discussion of a very similar list a week ago, a loud minority confuses “not Turing complete” with “sandboxed”. Hence lots of discussions about security that seem to miss the point.
The C++ templates example is kind of a meme, and Bjarne has pushed back on the idea that it was "accidental."
Sure, they didn't set out saying "we want to design a Turing-complete generics system" (because what kind of problem statement is that?), but templates were explicitly designed to be as general-purpose as possible. Turing-completeness was the result of that design goal:
"...I had aimed for generalty (and gotten Turing completeness modulo translation limits). I opposed restrictions to C++ immediately when Erwin Unruh presented what is widely believed to be the first template metaprogram to the ISO Standards committee's evolution working group."
If a config file isn't deterministic (because it's executable and can read info from its environment), then it can be harder for tools to introspect on the full config (imagine an IDE showing your project's settings or a tool that validates it; the tool would be blind to what your config specifies in environments the tool doesn't test with) or know when it's safe to cache the config's result (because the tool doesn't necessarily know whether the environment may have changed in a way the config cares about). (Extreme example: if you had a software library that declared its list of dependencies in an executable config file, and that config file could arbitrarily read the environment, maybe toggling certain dependencies depending on your platform and whether you had certain pre-requisites on your system, then a package repository that the library is published on can't show a canonical list of the library's dependencies. When a user wants to install the library and its dependencies, the package repository server can't respond with library and its dependencies together, because the library's dependencies for you could only be found out by executing its executable dependency config on your computer specifically, so the server would need to send you the library, your computer would need run the dependency config, and then go back and ask the server for the dependencies, and then repeat for their depedencies, etc.)
Also, executable config files (deterministic or not) aren't so easy or pretty to programmatically modify. If the config file can define arbitrary functions and use them to compute the config, then if you want to tweak the config with a tool like an IDE or package manager, then it will need to try to recognize a pattern in the config file, or add a chunk of code at the bottom that just mutates the config file after your handwritten code.
But if a system allows code execution on its host CPU, and the host CPU is Turing complete, this means the system itself is Turing complete too by extension.
As a D user, I highly doubt that, considering we had raytracers written in templates fourteen years and one major language version ago. [1] What stops them?
There is a guy who run Doom with only mov instructions, but it is of course incredibly slow, one frame every 7 hours :) [2]
[1]: https://news.ycombinator.com/item?id=9751312
[2]: https://news.ycombinator.com/item?id=16218872