Open Thread, May 25 - May 31, 2015

Gondolinian

If it's worth saying, but not worth its own post (even in Discussion), then it goes here.

Notes for future OT posters:

1. Please add the 'open_thread' tag.

2. Check if there is an active Open Thread before posting a new one. (Immediately before; refresh the list-of-threads page before posting.)

3. Open Threads should be posted in Discussion, and not Main.

4. Open Threads should start on Monday, and end on Sunday.

If it's worth saying, but not worth its own post (even in Discussion), then it goes here.

Notes for future OT posters:

1. Please add the 'open_thread' tag.

2. Check if there is an active Open Thread before posting a new one. (Immediately before; refresh the list-of-threads page before posting.)

3. Open Threads should be posted in Discussion, and not Main.

4. Open Threads should start on Monday, and end on Sunday.

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.

You first need to realize that Turing machine were invented before the first computer was ever built, and they were born as a mathematical model, an ideal construction.
The problem at the time was that there were certain natural classifications of functions on natural numbers, the recursive functions, and the Turing machine model helped to understand that partial recursive functions = computable functions.
Computable, at the time, meant that a human being was able to calculate them with the aid of pen and paper.

Nowadays, depending on the branch of computer s... (read more)

1D_Malik11y

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).