= 27d567bc2d48d9f40e9ccc20ea370b15)
D_Malik comments on Open Thread, May 25 - May 31, 2015 - Less Wrong Discussion
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (301)
I'm learning about Turing Machines for the first time. I think I get the gist of it, and I'm asking myself the question, "What's the big deal?". Here's my attempt at an answer:
Consider the idea of Thingspace. Things are there components/properties. You could plot a point in Thingspace that describes everything about, say John Smith.
You could encode that point in thingspace. Ie. you could create a code that says, "001010111010101001...1010101010101" represents point (42343,12312,11,343223423432423,...,123123123123) in Thingspace.
A Turing Machine seems like it basically says, "If the state is 0001010101011...10101011, change it to this." It's looking at things at a really really low level - the level of individual bits. These bits are a map that, in theory, seem to actually represent the territory with perfect accuracy (or really, it's capable of doing so).
So a Turing Machine could:
a) Look at a model of reality on the lowest level possible.
b) Manipulate a model of reality on the lowest level possible using a).
So back to the original question - what's the big deal? The big deal seems to be that "When you operate on such a low level, you could 'do anything'. The model could be perfectly accurate, and you aren't limited to making coarse adjustments to the model."
To what extent is my understanding accurate? Can anyone elaborate?
EDIT: It seems somewhat obvious that "if you had such precise control, you'd be able to perfectly model reality and all of that". But to me, the hard parts seem to be:
1) Creating a physical machine that does this. That has enough memory, that computes things quickly enough, and that is wired to do things based on state. (hardware)
2) Giving the machine the right instructions. (software)
I sense that these initial impressions are ignorant of something though - I just don't know what.
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).
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.)