Skip to main content

Questions tagged [recreational]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
26 votes
3 answers
5k views

Is Magic: the Gathering Turing complete?

A very specific question, I'm aware, and I doubt it will be answered by anyone that isn't already familiar with the rules of Magic. Cross-posted to Draw3Cards. Here are the comprehensive rules for the ...
30 votes
6 answers
3k views

Maximum computational power of a C implementation

If we go by the book (or any other version of the language specification if you prefer), how much computational power can a C implementation have? Note that “C implementation” has a technical meaning:...
17 votes
2 answers
4k views

Can chess simulate a Universal Turing Machine?

I am looking to get a definite answer to title question. Is there a set of rules that translates any program into a configuration of finite pieces on an infinite board, such that if black and white ...
18 votes
5 answers
2k views

Simple and practical deterministic algorithm, complicated running time

Very often, if the running time of an algorithm is a complicated expression, the algorithm itself is also complicated and impractical. Each of the cube roots and $\log \log n$ factors in the ...
8 votes
3 answers
516 views

Repeated Quine program

A Quine is a computer program which produces a copy of its own source code as its only output. Is there any Quine program that could print itself out n times, with n specified some way in the program?