You're looking at Less Wrong's discussion board. This includes all posts, including those that haven't been promoted to the front page yet. For more information, see About Less Wrong.

D_Malik comments on Open Thread, May 25 - May 31, 2015 - Less Wrong Discussion

3 Post author: Gondolinian 25 May 2015 12:00AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (301)

You are viewing a single comment's thread. Show more comments above.

Comment author: D_Malik 27 May 2015 08:44:33PM *  1 point [-]

Turing machines are a big deal because when you change the definition of a Turing machine (by letting it use arbitrarily many symbols, or giving it multiple tapes or a multi-dimensional tape, or letting it operate nondeterministically, or making its tape finite in one direction...) it usually can still solve exactly the same set of problems, which strongly suggests that Turing completeness is a "natural concept". A lot of computational systems are Turing-complete, and all of the discrete computational systems we've built are no more powerful than Turing machines. Physical reality might also be Turing-computable (Church-Turing-Deutsch principle), though we don't know that for sure (for instance, physics might involve infinite-precision calculations on non-computable numbers).

Comment author: Viliam 28 May 2015 09:35:12PM *  2 points [-]

An important property of Turing machines is that they have only one kind of instruction, which is very simple. That comes useful in various mathematical proofs, where you don't have to enumerate many options. (Try to imagine the horror of writing a mathematical proof that something cannot be solved by a C program.)