The author here writes:

Little known fact, the system of measuring length in the US is Turing complete

enter image description here

My question is: Is the system of measuring length in the US Turing complete?

  • 9
    $\begingroup$ I think the author means it as a joke. The measurement system, while certainly intricate and needlessly complex, doesn't look like the right kind of object to be Turing-Complete. It's just a weighted complete graph of conversion factors where the weight on $u\overset{w}{\rightarrow}v$ is the conversion factor from $u$ to $v$. As a stronger argument, this system preserves the parity of the input, in a sense: if $u\overset{a}{\rightarrow}v\overset{b}{\rightarrow}w$ then $u\overset{a\cdot b}{\rightarrow}w$ and $w\overset{\frac{1}{ab}}{\rightarrow}u$. Sorry to disappoint. $\endgroup$ – Lieuwe Vinkhuijzen May 19 '16 at 12:32
  • 2
    $\begingroup$ We do not have a senes of humor here. $\endgroup$ – Andrej Bauer May 19 '16 at 12:59
  • $\begingroup$ @AndrejBauer Perhaps we should have a new tag? $\endgroup$ – Hendrik Jan May 19 '16 at 14:01
  • 3
    $\begingroup$ What would it be, joke? In that case I propose we also introduce kitten-photo. $\endgroup$ – Andrej Bauer May 19 '16 at 14:12
  • 8
    $\begingroup$ @AndrejBauer Those would be tag synonyms for the real tags joke-recognition and furry-calculus-visualization respectively. Some more: for programming-related jokes I propose one-liner. For compiler fun questions -- jest-in-time along with jit as a type synonym. For computer architecture topics -- e-quip-ment. And, of course, we should get new badges: Joker(silver) and Wildcard(gold) -- *nix-pun intended. P.S. This question made my day! :) It's a pity it lacks some $\LaTeX$. $\endgroup$ – Anton Trunov May 19 '16 at 16:48

The post you're referring to is a joke: the US (and similar British Imperial) measurement systems are not Turing complete and the claim is an example of hyperbole.

A key feature that's necessary for a system to be Turing complete is that the system must include computations that do not terminate ("infinite loops"). Although it's not clear exactly what computations can be modeled by unit conversions (or what that even means!), any unit conversion within the diagram takes a finite number of steps.

| cite | improve this answer | |
  • 1
    $\begingroup$ Wow, it was a real question that got a real answer. $\endgroup$ – Andrej Bauer May 20 '16 at 8:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.