Questions tagged [recreational]
The recreational tag has no usage guidance.
5 questions
18
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 ...
- 219
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 ...
- 11.6k
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:...
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 ...
- 883
8
votes
3
answers
519
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?
- 361