Skip to main content
Computer Science

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

4
  • $\begingroup$ "Informally speaking, being Turing complete means that your mechanism can run any algorithm you could think of" Well, that relies on accepting the Church-Turing thesis, which says that Turing machines can implement any algorithm you can think of. Or, alternatively, you could take Turing machines as the definition of algorithm, in which case the informal statement is just an informal version of "can simulate any Turing machine" (which isn't a bad thing; just an observation). $\endgroup$ Commented Mar 14, 2017 at 22:29
  • $\begingroup$ My impression was that the OP asks about an intuitive understanding what it means to be turing complete. Hence, this kind of flippant, non-theoretical-computer-science answer. Thanks for pointing this out, I'll integrate it into the answer. @DavidRicherby $\endgroup$ Commented Mar 14, 2017 at 23:14
  • $\begingroup$ Thanks! That's the kind of answer I was looking for. I was thinking about the halting problem, and how languages with simple bounded for-loops are predictable (they always halt) - and thus non-Turing complete. I was thinking maybe being Turing-complete means being potentially unpredictable in some way (is chaotic the right term for those functions?) $\endgroup$ Commented Mar 15, 2017 at 15:25
  • $\begingroup$ @sashoalm, glad you like the answer. No, unpredictability does not really factor into the issue. Bounded for-loops (as non-tc) is a nice example, too. In fact, another good example for a simple (and more real-world) tc language would be one which just has variables and (unbounded) while - that is already enough to be tc. The (un)boundedness of the control structure is one of the key elements. $\endgroup$ Commented Mar 15, 2017 at 16:49