Skip to main content

Questions tagged [recreational]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
30 votes
6 answers

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:...
Gilles 'SO- stop being evil''s user avatar
26 votes
3 answers

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 ...
ripper234's user avatar
  • 883
18 votes
5 answers

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 ...
Jukka Suomela's user avatar
17 votes
2 answers

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 ...
TROLLHUNTER's user avatar
8 votes
3 answers

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?
huyichen's user avatar
  • 361