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*

7
  • 31
    $\begingroup$ Lookup the definition of "turing machine". There's no circular definition, since a turing machine is not defined as "being able to simulate another turing machine" - it's a fully designed theoretical computer (basically, an infinite tape state machine). You're just mixing up "turing-complete" and "turing machine". As far as I know, we still don't know of any algorithms that can't run on a turing machine, but that might be just my own ignorance. $\endgroup$ Commented Mar 13, 2017 at 14:10
  • 2
    $\begingroup$ @Luaan The Church-Turing Thesis would agree with you. $\endgroup$ Commented Mar 14, 2017 at 3:31
  • $\begingroup$ "Is there a way to define the capabilities of Turing Machine". Sure. Theory goes into how much space and time is required to solve algorithms with Turing machines (L, NL, P, NP, PSPACE, etc..), and there are also problems that cannot be solved (which can usually be solved by reductions to other unsolvable problems). One example of a problem that cannot be solved by Turing machines is the halting problem. $\endgroup$ Commented Mar 14, 2017 at 4:10
  • $\begingroup$ When it comes to CS (or any other) theory, it is always better to read a book on topic than to google it and read few blog posts on topic that are, in many cases, written by people who don't fully understand topic themselves. One good book will save you time, give you wider picture and better understanding. $\endgroup$ Commented Mar 14, 2017 at 13:00
  • $\begingroup$ The Ackermann function is a prominent example of something that a Turing machine can calculate but a more limited model of computation (primitive recursion) can't. $\endgroup$ Commented Mar 14, 2017 at 20:49