Turing Machine / Turing completeness?
Hello,
I've been programming for some years, and I've had a great interest in computers and technology in general for a very long time. However, I never really understood the importance of the Turing Machine / Turing Completeness model, which seems to be the holy grail of computer information systems - or something like that.
I'd be curious if there's anyone who can explain it to a simpleton like me. I don't have any formal education when it comes to computing, so that may have something to do with it. Basically, why is this model so popular? Why is it so important, and how does its importance reflect across things like programming?
Thanks for any input.
I've been programming for some years, and I've had a great interest in computers and technology in general for a very long time. However, I never really understood the importance of the Turing Machine / Turing Completeness model, which seems to be the holy grail of computer information systems - or something like that.
I'd be curious if there's anyone who can explain it to a simpleton like me. I don't have any formal education when it comes to computing, so that may have something to do with it. Basically, why is this model so popular? Why is it so important, and how does its importance reflect across things like programming?
Thanks for any input.
It's important because before you can begin to prove certain things about computation/computability, you need a formal definition of a computing machine. Real computers are way too complicated to define formally because they are so complex, but more importantly, they are all different. You can't prove something for each computer separately. So you make a model which captures the important properties that all computers have, specifically those that impose limitations.
Through the use of the model, you can prove things about what is and is not possible, or what is possible to do efficiently or not, and that can guide research decision; so you don't wast time trying to solve an impossible problem ( find an impossible algorithm ).
Also in cryptography, they are interested in finding algorithms that are impossible to solve efficiently, and incorporating them into encryption techniques. But they have to prove, or at least try to, that the problem is hard so they can be sure that the bad guys cannot break it.
The Turing machine is a prolific formal model of the computer. A whole lot of computer science theory is based on the model.
Some problems are called NP complete. Essentially, they are a set of problems that we do not know if they can be solved efficiently, but if one were solvable efficiently, then all of them would be. This is an example of the types of proofs and theory that rely on the turning machine.
Through the use of the model, you can prove things about what is and is not possible, or what is possible to do efficiently or not, and that can guide research decision; so you don't wast time trying to solve an impossible problem ( find an impossible algorithm ).
Also in cryptography, they are interested in finding algorithms that are impossible to solve efficiently, and incorporating them into encryption techniques. But they have to prove, or at least try to, that the problem is hard so they can be sure that the bad guys cannot break it.
The Turing machine is a prolific formal model of the computer. A whole lot of computer science theory is based on the model.
Some problems are called NP complete. Essentially, they are a set of problems that we do not know if they can be solved efficiently, but if one were solvable efficiently, then all of them would be. This is an example of the types of proofs and theory that rely on the turning machine.
Last edited on
If you want a nice intro to P vs NP, I found this video to be quite educational:https://www.youtube.com/watch?v=pTeZP-XfuKI
You can just read the wiki page on Turing completeness if you want to understand it.
You can just read the wiki page on Turing completeness if you want to understand it.
Topic archived. No new replies allowed.