Thread: Computation theory question

Why do I feel like for the past week and a half Clyde has been sitting in front of a homework paper with a check box for "Yes" and one for "No" waiting for a straight answer?

I'm way past homework . The question was actually motivated by reading neuroscience stuff.

So the answer is... anything is possible.
And mainly this is so because... turing machines don't exist.

Really? I thought computers used the Von Neuman architecture and the Von Neuman architecture was a way of making a universal turing machine. I thought my PC was a universal Turing machine. I've made a mistake?

Yup. You've made a mistake. Your computer is not a Turing Machine, much less an UTM.

Yup. You've made a mistake. Your computer is not a Turing Machine, much less an UTM.

Cool, thanks for the link, now i must discover why this:

The difference lies only with the ability of a Turing machine to manipulate an unbounded amount of data. However, given a finite amount of time, a Turing machine (like a real machine) can only manipulate a finite amount of data.

leads to this:

One way in which Turing machines are a poor model for programs is that many real programs, such as operating systems and word processors, are written to receive unbounded input over time, and therefore do not halt. Turing machines do not model such ongoing computation well (but can still model portions of it, such as individual procedures).

I'm not sure it really alters the natyre of my question, - which is basically given all the physical information is it always feasible to unravel the underlying logic. Never the less i am gratefull for the clarification.

It may look like a contradiction at first. However, the answer lies a few paragraphs before.

Arguably this is an hard concept to understand, since our brain cannot model very well the workings of a Turing machine. Only maths can model it. This is ironic because our brain is probably the only turing machine currently in existence in the world. However, I belive the key in understanding TMs and the answer to that apparent contradiction you explored is that TMs, contrary to any man-made machine to date, are not finit deterministic machines.

In the world of machines to this date, given a current state and a condition, you can only have one transition state. We observe this behavior in the real world out there; A door is closed. If we open it we set an open state. And if we close it we set a close state. We can at best formulate from this state machine and expand it using other state processes. If the door is open a draft state is set. If it is closed the draft state is cancelled. However each transition state table is a contained finit and deterministic unit. Computers simply cannot process infinit non-deterministic states. That's what intelligence does.

The maths behind the description of finit state machines and turing machines are well beyond my capabilities. However, the resulting concept is more or less the above.

A turing machine is not necessarily a sentient being though. It is simply an hypothesis of a machine that can process infinit and non-deterministic states. A turing machine would probably, for instance, be able to produce random numbers much the same way we humans do, however it would be incapable of using that information for anything more than what it was programmed to do.

We can simulate turing machines by tricking our computers (and our brains) into thinking we are working with an infinit non-deterministic set of information and states. However, it's all hocus pocus. As the random tables in any computer are. Just a trick to simulate.

We cannot build turing machines... yet.

Computers simply cannot process infinit non-deterministic states. That's what intelligence does.

Hmm i must confess that I don't think intelligence processes an infinite number of states - presumably a neuron can only be a finite (though possibly absurdly large) number of states.

It is simply an hypothesis of a machine that can process infinit and non-deterministic states.

I understand why you refer to the infinite part bit but i'm pretty sure there are both deterministic and non-deterministic turing machines. Which checking wiki seems to be right:

http://en.wikipedia.org/wiki/Turing_...uring_machines

So i'm not so sure whether the non-determinsitic part is necessarily the important bit.

Thanks for explaining your view though.