Questions tagged [recreational]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
16
votes
2answers
2k 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
5answers
1k 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 ...
28
votes
6answers
2k 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:...
24
votes
3answers
4k 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 ...
8
votes
3answers
448 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?