patternMinor
motivation and idea of defining non-deterministic Turing machine
Viewed 0 times
ideanonmotivationdeterministicmachineandturingdefining
Problem
This is a very basic question but I spent some time reading and find no answer. I am not computer science majored but have read some basic algorithm stuff, for example, some basic sorting algorithms and I also have some basic knowledge of how computers operate. However, I am really interested in the idea of a Turing machine, especially the non-deterministic one.
I have read Wiki about the definitions of a Turing machine (and watched some youtube videos) and I sort of accept that, although I really feel that this is a huge jump from an algorithm to an abstract machine. From my understanding (you are more than welcome to correct me):
So, Turing machine looks like a machine to realize any algorithm to solve problems. One just "translates" any algorithm to a set of mysterious simple rules (i.e. the partial function) and let the machine do the laboring job and then we get the solution.
In this respect, Turing machine is always deterministic, because algorithms are deterministic. It tells you what to do next precisely. This is no uncertainty. Turing machine is just a machine to realize any algorithm.
OK, This is very abstract and I sort of accept it. However, then I read something called non-deterministic Turing machine (NTM) and then I was knocked down. A NTM is pretty
I have read Wiki about the definitions of a Turing machine (and watched some youtube videos) and I sort of accept that, although I really feel that this is a huge jump from an algorithm to an abstract machine. From my understanding (you are more than welcome to correct me):
- A Turing machine is a machine performing works specified on a cookery book (algorithm).
- The pages of the cookery book represent the "states" of your machine and each page contains a table saying that which state and which cell your machine will move to given the alphabet the machine read and your current state. (NB. This is not a function but a partial function because it is possible that the machine stops.)
- So, to guess the idea and motivation of defining an abstract Turing machine, I imagine that the algorithm corresponds to the partial map, the memory of the computer corresponds to the (infinitely long) tape and what's finally on the tape is the answer to the question you wanna solve.
So, Turing machine looks like a machine to realize any algorithm to solve problems. One just "translates" any algorithm to a set of mysterious simple rules (i.e. the partial function) and let the machine do the laboring job and then we get the solution.
In this respect, Turing machine is always deterministic, because algorithms are deterministic. It tells you what to do next precisely. This is no uncertainty. Turing machine is just a machine to realize any algorithm.
OK, This is very abstract and I sort of accept it. However, then I read something called non-deterministic Turing machine (NTM) and then I was knocked down. A NTM is pretty
Solution
Could someone explain to me why we need such multiple options? I would never expect to encounter something uncertainty in the implementation of an algorithm.
I think this is your primary misconception: an NTM is not supposed to be a realistic machine. That is, no one has ever tried to build a NTM, no one knows how to implement it, and algorithms in the real world are not written in this way with "multiple options".
An NTM is, instead, supposed to be a hypothetical more powerful computer; in contrast to the Turing machine, which corresponds to real computers, NTMs can do even more. Why can they do more? Basically, because they can branch off on several different options, or parallel universes; and they accept a string if and only if one of those universes accepts. A regular Turing machine corresponds to just having one parallel universe.
Let's see an example. Consider the following problem: Given as input an integer $x$, is the square root of $x$ an integer? Accept if yes, reject if no.
-
A Turing machine would have to do some math and figure out how to calculate the square root. So we have to do the hard work of designing a correct algorithm :(
-
An NTM doesn't have to do any of that hard work, and can just cheat :) It works in the following way: just nondeterministically guess the number $y$. Then check if $y^2 = x$. If so, accept.
This is how NTMs are unrealistic: they can just cheat and try all possibilities in different universes, even though when we know in the real world that this is impossible.
For example, if we input $9$ to the NTM we just described,
then there are lots of parallel universes that try different values of $y$: one tries $y = 1$, one tries $y = 2$, one tries $y = 3$, one tries $y = 4$, and so on. In many of these universes the NTM does the wrong thing: for example, it picks $y = 4$ and finds that $4^2 \ne 9$, and rejects (incorrectly). But those universes are just ignored; we don't care about them. The only thing that matters is that there is some universe where the machine accepts, namely the universe where we picked $y = 3$, and found that $3^2 = 9$.
It is like telling the machine: you first do A, then if you find yourself in a state B and find the data is now B' then you choose for yourself one of the 10 allowed next steps?
It isn't exactly like "choosing for yourself"; it's that each choice is tried in a different parallel universe.
Are NTM's corresponding to a set of algorithms that need uncertainty? for example the generation of random numbers?
No, they are a little bit different than uncertainty choosing random numbers, mainly because we only care about the parallel universes where the machine accepts (in particular, we care if there is at least one parallel universe where it accepts), and we ignore all the universes where the machine rejects.
If no, why do we need to allow multiple choices for a Turing machine?
We don't need them to describe real computations, but they are a useful tool for understanding the limits of computation. In particular, there are many problems that NTMs can solve efficiently, that we don't know how to solve efficiently with TMs; these are the famous "NP-complete" problems, and it is useful in practice to know what problems will be hard to design an algorithm for.
In this sense, an NTM looks like a multi-threading parallelization to save time?
Yes, it is a lot like this, except a little bit less general: the thing is that the multiple parallel universes cannot communicate, but they only work independently, and then we care if at least one universe accepts.
In other words, with a multi-threading machine, you could try lots of different parallel threads, and then at the end you could have all the threads come together, and then decide what to do with all the outputs of the different threads. NTMs can't do that; they just spawn off lots of parallel universes and accept if at least one universe accepts.
Another difference (in terms of practicality) is that multi-threading on a real computer usually only allows for a small (probably constant) number of parallel threads. On the other hand, NTMs can spawn off as many parallel universes as you like; if the input is size $n$, they often might spawn of $2^n$ threads, which is a larger number than is possible in practice. This is why NTMs are not a realistic type of machine, and are just a theoretical object of study.
I think this is your primary misconception: an NTM is not supposed to be a realistic machine. That is, no one has ever tried to build a NTM, no one knows how to implement it, and algorithms in the real world are not written in this way with "multiple options".
An NTM is, instead, supposed to be a hypothetical more powerful computer; in contrast to the Turing machine, which corresponds to real computers, NTMs can do even more. Why can they do more? Basically, because they can branch off on several different options, or parallel universes; and they accept a string if and only if one of those universes accepts. A regular Turing machine corresponds to just having one parallel universe.
Let's see an example. Consider the following problem: Given as input an integer $x$, is the square root of $x$ an integer? Accept if yes, reject if no.
-
A Turing machine would have to do some math and figure out how to calculate the square root. So we have to do the hard work of designing a correct algorithm :(
-
An NTM doesn't have to do any of that hard work, and can just cheat :) It works in the following way: just nondeterministically guess the number $y$. Then check if $y^2 = x$. If so, accept.
This is how NTMs are unrealistic: they can just cheat and try all possibilities in different universes, even though when we know in the real world that this is impossible.
For example, if we input $9$ to the NTM we just described,
then there are lots of parallel universes that try different values of $y$: one tries $y = 1$, one tries $y = 2$, one tries $y = 3$, one tries $y = 4$, and so on. In many of these universes the NTM does the wrong thing: for example, it picks $y = 4$ and finds that $4^2 \ne 9$, and rejects (incorrectly). But those universes are just ignored; we don't care about them. The only thing that matters is that there is some universe where the machine accepts, namely the universe where we picked $y = 3$, and found that $3^2 = 9$.
It is like telling the machine: you first do A, then if you find yourself in a state B and find the data is now B' then you choose for yourself one of the 10 allowed next steps?
It isn't exactly like "choosing for yourself"; it's that each choice is tried in a different parallel universe.
Are NTM's corresponding to a set of algorithms that need uncertainty? for example the generation of random numbers?
No, they are a little bit different than uncertainty choosing random numbers, mainly because we only care about the parallel universes where the machine accepts (in particular, we care if there is at least one parallel universe where it accepts), and we ignore all the universes where the machine rejects.
If no, why do we need to allow multiple choices for a Turing machine?
We don't need them to describe real computations, but they are a useful tool for understanding the limits of computation. In particular, there are many problems that NTMs can solve efficiently, that we don't know how to solve efficiently with TMs; these are the famous "NP-complete" problems, and it is useful in practice to know what problems will be hard to design an algorithm for.
In this sense, an NTM looks like a multi-threading parallelization to save time?
Yes, it is a lot like this, except a little bit less general: the thing is that the multiple parallel universes cannot communicate, but they only work independently, and then we care if at least one universe accepts.
In other words, with a multi-threading machine, you could try lots of different parallel threads, and then at the end you could have all the threads come together, and then decide what to do with all the outputs of the different threads. NTMs can't do that; they just spawn off lots of parallel universes and accept if at least one universe accepts.
Another difference (in terms of practicality) is that multi-threading on a real computer usually only allows for a small (probably constant) number of parallel threads. On the other hand, NTMs can spawn off as many parallel universes as you like; if the input is size $n$, they often might spawn of $2^n$ threads, which is a larger number than is possible in practice. This is why NTMs are not a realistic type of machine, and are just a theoretical object of study.
Context
StackExchange Computer Science Q#116180, answer score: 5
Revisions (0)
No revisions yet.