8 ms·

Turing completeness bullshit

65 points by fogus 15y ago

cleverjake 15y ago
While I agree that it is a bit of a misnomer to say that anything is possible in a turing complete language from a feasibility stand point, I think this response falls back to a common thought process that technical minded people go through - literal answers. Of course it is possible to do it, it may just be incredibly difficult. When most people ask if they can do X in Foo, they are usually asking if it is a good idea to do X in Foo. Should the person being asked tell them no even if it is a possibility that is not easy?
- damncabbage 15y ago
  I think it's also due to some people kinda-sorta understanding what Turing Completeness means, and then applying it to everything to sound smart.
- p4wnc6 15y ago
  I agree. The OP blog post is mistaking. I think the real language misuse is on the behalf of Person A. When asking whether you "can do something in the Foo programming language" this could be a question of theoretical universality or a question of practicality. If it's one of practicality, then it has nothing to do with Turing universality. If it's theoretical, as in "is Foo expressive enough to describe such and such a computation at all", then universality matters. Also, from a computationalist's perspective in Philosophy, Turing completeness literally does mean being able to do anything that a single-taped Turing machine can do (such as writing a GUI or writing to a screen). If you a priori disconnect your Turing machine from the screen, effectively eliminating the logical possibility to print to it (or, similarly, you use some pared down language where specific functionality is intentionally left out) then it makes no sense at all to bring Turing completeness into it. It seems like the OP either rejects the Extended Church Turing thesis, or mistakenly thinks that other people lump all possible hardware limitations into Turing completeness. If a language is resource bounded, then it is only Turing complete w.r.t. a Turing machine that has the same resource bounds.
  - 5hoom 15y ago
    Wonderfully put, thank you.
  - z92 15y ago
    Needs paragraph break.
    - Despite 15y ago
      I disagree. The paragraphs were comprehensible and held together by subject matter. I had no trouble reading them.
      - p4wnc6 15y ago
        To be fair, originally I had them in one paragraph, then edited them.
  - andreasvc 15y ago
    > anything that a single-taped Turing machine can do (such as writing a GUI or writing to a screen). Wait, those are the things a Turing machine CANNOT do! A Turing machine has no input or output, the computation it defines is purely a function of what's on its tape before and after its work (when it halts). > If you a priori disconnect your Turing machine from the screen Again this makes no sense, the ('a priori') defintion of a Turing machine does not include a screen, so there's nothing to disconnect. It's really just the tape. And no, it's quite a stretch to claim that person A could be talking about universality, the blog post says he was asking about GUIs so that's squarely a practical question. > or [...] thinks that other people lump all possible hardware limitations into Turing completeness. I have no idea how you arrive at this from the blog post.
    - p4bl0 15y ago
      OP here. I was going to write just this, I didn't do it until now because I was on my phone and I wanted a real keyboard to answer. So thanks for doing it for me. As a side note, I'll add that "person A"s are people I know IRL and this troll (let's call it what it is) aimed at them, not HN audience ;-).
- podperson 15y ago
  Agreed (also agree with another post at this level). It seems like a clever "nit" to pick but the only thing you need to add to "turing complete" is "able to address memory in a reasonable way" (or "not sandboxed from memory") and you get everything the author is complaining about and you're back to square one (i.e. the language is "turing complete and has memory access". How do I print? I stick stuff in the right places in memory and set the program counter. How do I draw graphics? I stick stuff in the right place in memory and set the program counter.
wyuenho 15y ago
Ahhhh no I disagree. I think this is one of those 140 char limit short sound bite problems that often makes the people listening hard to understand. Turing Completeness is about computability, but also implies the functions in that class are able to simulate each other. So "theoretically", you COULD write an interpreter in Brainfuck without "," and "." that simulates language L by doing output using some other means, or representing it differently besides printing it out onto the screen. All it has to do is to leave an output state on a Turing Machine. Now the question, when people talk about "Foo is Turing complete so you can do everything.", is this really what they mean? Probably not, most of them only say this half-jokingly. It's theoretically possible, it's just very unpractical in reality. I'm nonetheless equally annoyed by the term "general purpose language" for the reasons pointed in the post tho.
- phillmv 15y ago
  You could presumably write a "Limited Brainfuck" compiler and then write an interpreter for any language you want into that :P. If it's complete, it's turtles all the way down.
  - wyuenho 15y ago
    Exactly, that's why my mind screams "BS" every time I hear the term "general purpose language".
cyrus_ 15y ago
Alan Perlis coined the term "Turing tarpit" for this in one of his Epigrams on Programming. http://en.wikipedia.org/wiki/Turing_tarpit http://en.wikipedia.org/wiki/Turing_tarpit
RockyMcNuts 15y ago
If you can do a test, a loop, and a write, you're Turing complete IIRC. Hell, the DOS shell is Turing complete, your HP-12C is Turing complete. So ANSI SQL with selects only may not be Turing complete, but pretty much all SQL implementations are, since they added loops, not to mention stored procedures etc. All languages are Turing complete and equivalent from a computability standpoint. That's the sense in which it means nothing for a language to be Turing complete - they all are. They are different in terms of expressive power, computational efficiency for different problems. Can you do closures in HP-12C assembler? Of course! just write a Lisp interpreter in assembler, and there you go.
- xyzzyz 15y ago
  The posts like yours are the ones that actually create confusion around this term, because their authors are confused on what the Turing completeness is themselves, and so they spread their confusion on the others. No, tests and loops are not what make computational stuff Turing complete -- nondeterministic finite automatons have both of them, and yet they're very weak computationally. I/O (assuming that's what you mean by write) is not even relevant. What matters the most is _memory_, and more importantly, _infinite, easily accessible_ memory. Nondeterministic finite automata have only finite amount of memory available, and thus they are very constrained on what they can compute. Nondeterministic pushdown automata, in spite of having infinite amount of memory available, don't have an easy access to it, and so, being stronger than finite automata, they're still weaker than Turing machines. But as soon as you add a second stack to a pushdown automaton, it suddenly becomes Turing complete. Hell, you can do it even with 6 integer variables instead of 2 stacks (I recall from my computation theory course that 3 integer variables are enough to encode a stack, so 6 will give you two stacks. Maybe you can go down even to 5 or 4). However, you absolutely require infinite memory, because, for sane definitions of "memory", every device with finite amount of memory (for instance, x86 PC) will not be able to compute anything more than deterministic finite automaton. From this point of view, all our computers are able to do is to match its input to a long and hairy regular expression. I hope that it will help some people realize how irrelevant is Turing completeness notion when it's used with regard to real life stuff.
  - 15y ago
gfodor 15y ago
You think that's bad? I'll raise you the "the halting problem proves that you can never prove a program halts" claim.
- baddox 15y ago
  The two statements aren't really analogous. Yours is simply incorrect, while the one in the article is a correct (factual) response that's just not helpful.
  - mihaifm 15y ago
    What's so incorrect about this statement?
    - alok-g 15y ago
      >> the halting problem proves that you can never prove a program halts Halting problem proves that you can never prove an "arbitrary" program halts. A specific program can of course be proven to halt or not halt. The above statement is often misused to state that day-to-day PC programs can never be proven to be bug-free (even in theory).
      - baddox 15y ago
        Aye, I always think of the halting problem as "if the program is still running, you can't necessarily know if it will ever halt." If you see a program halt, after a millisecond or after 10 years, then you've obviously proven whether or not it halts. Also, while the halting problem doesn't necessarily say anything about bugs, there is a more general theorem that essentially says that you can't know in general if a program enjoys any non-trivial property (e.g. it prints a "1" at some point, it accesses the network, or it halts). I can't recall the name of the theorem, but the intuitive proof is similar to the halting problem's. This theorem does seem to hint that programs can't be proven to be bug-free in general.
        pmiller2 15y ago
InclinedPlane 15y ago
Turing completeness concerns itself with the ability of a computer to solve problems that are computable. Modern computers, however, are almost entirely purposed towards interacting with humans and processing data. Mathematically these "problems" are isomorphic, but the real world concerns itself with issues like correctness, robustness, performance, efficiency, cost, scalability, etc. The idea of turing completeness compares a 100% perfect program against another 100% perfect program. It does not concern itself at all with efficiency, which is horrific in and of itself, but worse yet it does not concern itself with the difficulty of creating and maintaining the program. Given that this tends to be the overwhelmingly largest factor in the cost of creating software this is a bit of a problem.
0x12 15y ago
Turing completeness deals with computability, not with the practicalities of IO and so on. To say that something is Turing complete simply means that you could implement a universal Turing machine, which can then run any other Turing machine as its program, and so can compute anything that is in theory (without any constraints on time and space) computable. I understand the authors aggravation with people throwing around the sentence 'x is Turing complete, so you can do anything in x' without any appreciation of the disconnect between the theoretical and the practical sides of this, but I think that it's use is more in jest than serious and that the author should possibly grow a sense of humor. Typical use: A: can you do 'x' in Perl B: Perl is Turing complete, of course you can do 'x'. Shows that person 'B' has a sense of humor and/or wants to get rid of the questioner without having to answer the question, not that they're clueless about the practicalities of this statement. It's analogous to 'google it', 'rtfm' or any one of another 100 ways in which people try to show their superiority over others or try to create an 'in' and and 'out' group. Think of it as just another meme and move on. Flagged.
- omaranto 15y ago
  Flagging a post because you think the author lacks a sense if humor seems harsh to me.
  - 0x12 15y ago
    No, I've flagged it because this 'Turing Completeness Bullshit' is not bullshit, but the article is. Turing completeness actually has a use and railing against the people that use it in a manner that it was never intended to be used in is a total waste of time. The article author seems to agree with that assessment, see: http://news.ycombinator.com/item?id=3047002 http://news.ycombinator.com/item?id=3047002
    - raganwald 15y ago
      Flagging is not for disagreement, it's for spam, off-topic posts, and link-jacking. You flagged this article because HN doesn't have a down vote for articles, but what you are really doing is messing up the spam filters by training them that words like "Turing" are associated with articles that may get flagged. Please do not flag articles simply because you think they are wrong. Express your disagreement and move on.

65 points by fogus 15y ago

While I agree that it is a bit of a misnomer to say that anything is possible in a turing complete language from a feasibility stand point, I think this response falls back to a common thought process that technical minded people go through - literal answers. Of course it is possible to do it, it may just be incredibly difficult. When most people ask if they can do X in Foo, they are usually asking if it is a good idea to do X in Foo. Should the person being asked tell them no even if it is a possibility that is not easy?

damncabbage 15y ago
I think it's also due to some people kinda-sorta understanding what Turing Completeness means, and then applying it to everything to sound smart.
p4wnc6 15y ago
I agree. The OP blog post is mistaking. I think the real language misuse is on the behalf of Person A. When asking whether you "can do something in the Foo programming language" this could be a question of theoretical universality or a question of practicality. If it's one of practicality, then it has nothing to do with Turing universality. If it's theoretical, as in "is Foo expressive enough to describe such and such a computation at all", then universality matters. Also, from a computationalist's perspective in Philosophy, Turing completeness literally does mean being able to do anything that a single-taped Turing machine can do (such as writing a GUI or writing to a screen). If you a priori disconnect your Turing machine from the screen, effectively eliminating the logical possibility to print to it (or, similarly, you use some pared down language where specific functionality is intentionally left out) then it makes no sense at all to bring Turing completeness into it. It seems like the OP either rejects the Extended Church Turing thesis, or mistakenly thinks that other people lump all possible hardware limitations into Turing completeness. If a language is resource bounded, then it is only Turing complete w.r.t. a Turing machine that has the same resource bounds.
- 5hoom 15y ago
  Wonderfully put, thank you.
- z92 15y ago
  Needs paragraph break.
  - Despite 15y ago
    I disagree. The paragraphs were comprehensible and held together by subject matter. I had no trouble reading them.
    - p4wnc6 15y ago
      To be fair, originally I had them in one paragraph, then edited them.
- andreasvc 15y ago
  > anything that a single-taped Turing machine can do (such as writing a GUI or writing to a screen). Wait, those are the things a Turing machine CANNOT do! A Turing machine has no input or output, the computation it defines is purely a function of what's on its tape before and after its work (when it halts). > If you a priori disconnect your Turing machine from the screen Again this makes no sense, the ('a priori') defintion of a Turing machine does not include a screen, so there's nothing to disconnect. It's really just the tape. And no, it's quite a stretch to claim that person A could be talking about universality, the blog post says he was asking about GUIs so that's squarely a practical question. > or [...] thinks that other people lump all possible hardware limitations into Turing completeness. I have no idea how you arrive at this from the blog post.
  - p4bl0 15y ago
    OP here. I was going to write just this, I didn't do it until now because I was on my phone and I wanted a real keyboard to answer. So thanks for doing it for me. As a side note, I'll add that "person A"s are people I know IRL and this troll (let's call it what it is) aimed at them, not HN audience ;-).
podperson 15y ago
Agreed (also agree with another post at this level). It seems like a clever "nit" to pick but the only thing you need to add to "turing complete" is "able to address memory in a reasonable way" (or "not sandboxed from memory") and you get everything the author is complaining about and you're back to square one (i.e. the language is "turing complete and has memory access". How do I print? I stick stuff in the right places in memory and set the program counter. How do I draw graphics? I stick stuff in the right place in memory and set the program counter.

wyuenho 15y ago

Ahhhh no I disagree. I think this is one of those 140 char limit short sound bite problems that often makes the people listening hard to understand. Turing Completeness is about computability, but also implies the functions in that class are able to simulate each other. So "theoretically", you COULD write an interpreter in Brainfuck without "," and "." that simulates language L by doing output using some other means, or representing it differently besides printing it out onto the screen. All it has to do is to leave an output state on a Turing Machine. Now the question, when people talk about "Foo is Turing complete so you can do everything.", is this really what they mean? Probably not, most of them only say this half-jokingly. It's theoretically possible, it's just very unpractical in reality. I'm nonetheless equally annoyed by the term "general purpose language" for the reasons pointed in the post tho.

phillmv 15y ago
You could presumably write a "Limited Brainfuck" compiler and then write an interpreter for any language you want into that :P. If it's complete, it's turtles all the way down.
- wyuenho 15y ago
  Exactly, that's why my mind screams "BS" every time I hear the term "general purpose language".

cyrus_ 15y ago

Alan Perlis coined the term "Turing tarpit" for this in one of his Epigrams on Programming. http://en.wikipedia.org/wiki/Turing_tarpit http://en.wikipedia.org/wiki/Turing_tarpit

RockyMcNuts 15y ago

If you can do a test, a loop, and a write, you're Turing complete IIRC. Hell, the DOS shell is Turing complete, your HP-12C is Turing complete. So ANSI SQL with selects only may not be Turing complete, but pretty much all SQL implementations are, since they added loops, not to mention stored procedures etc. All languages are Turing complete and equivalent from a computability standpoint. That's the sense in which it means nothing for a language to be Turing complete - they all are. They are different in terms of expressive power, computational efficiency for different problems. Can you do closures in HP-12C assembler? Of course! just write a Lisp interpreter in assembler, and there you go.

xyzzyz 15y ago
The posts like yours are the ones that actually create confusion around this term, because their authors are confused on what the Turing completeness is themselves, and so they spread their confusion on the others. No, tests and loops are not what make computational stuff Turing complete -- nondeterministic finite automatons have both of them, and yet they're very weak computationally. I/O (assuming that's what you mean by write) is not even relevant. What matters the most is _memory_, and more importantly, _infinite, easily accessible_ memory. Nondeterministic finite automata have only finite amount of memory available, and thus they are very constrained on what they can compute. Nondeterministic pushdown automata, in spite of having infinite amount of memory available, don't have an easy access to it, and so, being stronger than finite automata, they're still weaker than Turing machines. But as soon as you add a second stack to a pushdown automaton, it suddenly becomes Turing complete. Hell, you can do it even with 6 integer variables instead of 2 stacks (I recall from my computation theory course that 3 integer variables are enough to encode a stack, so 6 will give you two stacks. Maybe you can go down even to 5 or 4). However, you absolutely require infinite memory, because, for sane definitions of "memory", every device with finite amount of memory (for instance, x86 PC) will not be able to compute anything more than deterministic finite automaton. From this point of view, all our computers are able to do is to match its input to a long and hairy regular expression. I hope that it will help some people realize how irrelevant is Turing completeness notion when it's used with regard to real life stuff.
- 15y ago

gfodor 15y ago

You think that's bad? I'll raise you the "the halting problem proves that you can never prove a program halts" claim.

baddox 15y ago
The two statements aren't really analogous. Yours is simply incorrect, while the one in the article is a correct (factual) response that's just not helpful.
- mihaifm 15y ago
  What's so incorrect about this statement?
  - alok-g 15y ago
    >> the halting problem proves that you can never prove a program halts Halting problem proves that you can never prove an "arbitrary" program halts. A specific program can of course be proven to halt or not halt. The above statement is often misused to state that day-to-day PC programs can never be proven to be bug-free (even in theory).
    - baddox 15y ago
      Aye, I always think of the halting problem as "if the program is still running, you can't necessarily know if it will ever halt." If you see a program halt, after a millisecond or after 10 years, then you've obviously proven whether or not it halts. Also, while the halting problem doesn't necessarily say anything about bugs, there is a more general theorem that essentially says that you can't know in general if a program enjoys any non-trivial property (e.g. it prints a "1" at some point, it accesses the network, or it halts). I can't recall the name of the theorem, but the intuitive proof is similar to the halting problem's. This theorem does seem to hint that programs can't be proven to be bug-free in general.
      - pmiller2 15y ago

InclinedPlane 15y ago

Turing completeness concerns itself with the ability of a computer to solve problems that are computable. Modern computers, however, are almost entirely purposed towards interacting with humans and processing data. Mathematically these "problems" are isomorphic, but the real world concerns itself with issues like correctness, robustness, performance, efficiency, cost, scalability, etc. The idea of turing completeness compares a 100% perfect program against another 100% perfect program. It does not concern itself at all with efficiency, which is horrific in and of itself, but worse yet it does not concern itself with the difficulty of creating and maintaining the program. Given that this tends to be the overwhelmingly largest factor in the cost of creating software this is a bit of a problem.

0x12 15y ago

Turing completeness deals with computability, not with the practicalities of IO and so on. To say that something is Turing complete simply means that you could implement a universal Turing machine, which can then run any other Turing machine as its program, and so can compute anything that is in theory (without any constraints on time and space) computable. I understand the authors aggravation with people throwing around the sentence 'x is Turing complete, so you can do anything in x' without any appreciation of the disconnect between the theoretical and the practical sides of this, but I think that it's use is more in jest than serious and that the author should possibly grow a sense of humor. Typical use: A: can you do 'x' in Perl B: Perl is Turing complete, of course you can do 'x'. Shows that person 'B' has a sense of humor and/or wants to get rid of the questioner without having to answer the question, not that they're clueless about the practicalities of this statement. It's analogous to 'google it', 'rtfm' or any one of another 100 ways in which people try to show their superiority over others or try to create an 'in' and and 'out' group. Think of it as just another meme and move on. Flagged.

omaranto 15y ago
Flagging a post because you think the author lacks a sense if humor seems harsh to me.
- 0x12 15y ago
  No, I've flagged it because this 'Turing Completeness Bullshit' is not bullshit, but the article is. Turing completeness actually has a use and railing against the people that use it in a manner that it was never intended to be used in is a total waste of time. The article author seems to agree with that assessment, see: http://news.ycombinator.com/item?id=3047002 http://news.ycombinator.com/item?id=3047002
  - raganwald 15y ago
    Flagging is not for disagreement, it's for spam, off-topic posts, and link-jacking. You flagged this article because HN doesn't have a down vote for articles, but what you are really doing is messing up the spam filters by training them that words like "Turing" are associated with articles that may get flagged. Please do not flag articles simply because you think they are wrong. Express your disagreement and move on.