Turing machines
My knowledge of how Turing machines function hasn't quite consolidated yet, although, I'd like to think this is a study in it's own right, I'm guessing it would fall under the computation theory umbrella.
My question is; Turing machines can compute any problem that is computationally possible, a problem could be as trivial as finding if a string is a palindrome but it could also be Microsoft excel, couldn't it be?..
So here's my crude understanding of how a Turing machine works: We could imagine it as a long tape divided into cells. We will have a head above that cell that can read(from the cell), write(to the cell) or move left or right. We also have states, each state will be looked up by symbol, each symbol will represent an instruction(move left. These instructions are written into a program, we could even store these states in a book and represent each state as a page.
We first place our head at position 0 on the tape, we look up the symbol of that particular state, we can then write or do nothing to that cell, we can then move right or left, and transition to the next state until we come across the final state which may print something such as the answer to our problem. And finally, we arrive on a halt position and accordingly, the machine halts.
It's been proven that languages like C++, Python, Java, etc are all Turing complete, meaning they can compute or solve any problem that is computationally possible. But how can something so simple as a piece of long tape with the ability to read, write and move to different states and positions on the tape possible be able to do something complex such as represent and also traversing a binary search tree, binary search on a search space/array, recursive factorial algorithms, etc??
Again Turing machines are said to be able to do everything and nothing more that a modern computer can do, but a Turing machine can't display a GUI?
My question is; Turing machines can compute any problem that is computationally possible, a problem could be as trivial as finding if a string is a palindrome but it could also be Microsoft excel, couldn't it be?..
So here's my crude understanding of how a Turing machine works: We could imagine it as a long tape divided into cells. We will have a head above that cell that can read(from the cell), write(to the cell) or move left or right. We also have states, each state will be looked up by symbol, each symbol will represent an instruction(move left. These instructions are written into a program, we could even store these states in a book and represent each state as a page.
We first place our head at position 0 on the tape, we look up the symbol of that particular state, we can then write or do nothing to that cell, we can then move right or left, and transition to the next state until we come across the final state which may print something such as the answer to our problem. And finally, we arrive on a halt position and accordingly, the machine halts.
It's been proven that languages like C++, Python, Java, etc are all Turing complete, meaning they can compute or solve any problem that is computationally possible. But how can something so simple as a piece of long tape with the ability to read, write and move to different states and positions on the tape possible be able to do something complex such as represent and also traversing a binary search tree, binary search on a search space/array, recursive factorial algorithms, etc??
Again Turing machines are said to be able to do everything and nothing more that a modern computer can do, but a Turing machine can't display a GUI?
Last edited on
You can think of it as how your C++ code turns into Assembly which then becomes 1s and 0s. You may say, "how can a string of 1s and 0s create Microsoft Excel!?" but that's exactly what does happen.
All code is simply logic. A Turing Machine is a machine that can compute any logic that is possible to compute. Therefore, a Turing Machine can compute any code that exists. Now, going from theory to actually making a Turing Machine that would actually run Microsoft Excel would be an arduous task. Practically, you can't do it. Not that it's impossible, but the work you'd have to put in would make no sense at all for why you should do it.
You can see for yourself this is true by learning about DFAs. You can write out a simple program, (perhaps one that checks if a number is a palindrome) then create a DFA with the same logic.
The DFA could be turned into a long tape as you've described that does the same thing.
Just because code gets progressively more complex as you go doesn't mean that you can't still break it down to simple logic.
It could if you were able to connect it to one properly.
You can display to a screen using a Microprocessor and a small screen. You can create your own logic for how to talk to the screen (similar to how the microprocessor would), ditch the microprocessor, and have turn the logic into a DFA (you probably will have to change the logic around to get it into a DFA).
You can then turn the DFA into a long tape. Now, getting each state to send the proper signal to the display would have to be done mechanically, but you could theoretically do it!
But really, I wouldn't worry too much about Turing Machines. The idea of Turing Completeness is whether a given computation machine can execute any logic given to it. The idea isn't very important as an average programmer. Every language you code in is going to be Turing complete.
You can see how C++ is Turing complete, but you still don't want to use it for certain applications just because of how complicated and obtuse the code would have to be!
A Turing Machine can replicate any program. This is true in theory, and so you can generate any program as a Turing Machine. But if it were to be done for, lets say Microsoft Excel, the complexity of the machine would lose you.
All code is simply logic. A Turing Machine is a machine that can compute any logic that is possible to compute. Therefore, a Turing Machine can compute any code that exists. Now, going from theory to actually making a Turing Machine that would actually run Microsoft Excel would be an arduous task. Practically, you can't do it. Not that it's impossible, but the work you'd have to put in would make no sense at all for why you should do it.
You can see for yourself this is true by learning about DFAs. You can write out a simple program, (perhaps one that checks if a number is a palindrome) then create a DFA with the same logic.
The DFA could be turned into a long tape as you've described that does the same thing.
Just because code gets progressively more complex as you go doesn't mean that you can't still break it down to simple logic.
| but a Turning machine can't display a GUI? |
It could if you were able to connect it to one properly.
You can display to a screen using a Microprocessor and a small screen. You can create your own logic for how to talk to the screen (similar to how the microprocessor would), ditch the microprocessor, and have turn the logic into a DFA (you probably will have to change the logic around to get it into a DFA).
You can then turn the DFA into a long tape. Now, getting each state to send the proper signal to the display would have to be done mechanically, but you could theoretically do it!
But really, I wouldn't worry too much about Turing Machines. The idea of Turing Completeness is whether a given computation machine can execute any logic given to it. The idea isn't very important as an average programmer. Every language you code in is going to be Turing complete.
You can see how C++ is Turing complete, but you still don't want to use it for certain applications just because of how complicated and obtuse the code would have to be!
A Turing Machine can replicate any program. This is true in theory, and so you can generate any program as a Turing Machine. But if it were to be done for, lets say Microsoft Excel, the complexity of the machine would lose you.
Last edited on
At the machine's core level there isn't even 1s and 0s, that abstraction is just voltage potential differences.
Truly fascinating, really great post Zapshe :)
that makes sense, I'd imagine a complex algorithm or data structure would encompass a ridiculous amount of states.
A Turing machine cannot compute the halting problem, to me that doesn't make sense. We have a box that takes in the source code of a program and that box determines if the program will loop or halt. We then feed the output into another black box which will negate the result i.e. if the previous box halts then this box loops forever or if the previous box loops then this box halts.
I don't see how this logically doesn't make sense, we could indeed represent both these boxes as programs, program 'A' reads the source code and determines if it halts or loops. program 'B' takes the input of program 'A' and does the opposite
Surely if program 'B' loops forever then we know that program 'A's input must halt and likewise, if program 'B' halts then we can assume that program 'A's input must loop infinitely.
that makes sense, I'd imagine a complex algorithm or data structure would encompass a ridiculous amount of states.
A Turing machine cannot compute the halting problem, to me that doesn't make sense. We have a box that takes in the source code of a program and that box determines if the program will loop or halt. We then feed the output into another black box which will negate the result i.e. if the previous box halts then this box loops forever or if the previous box loops then this box halts.
I don't see how this logically doesn't make sense, we could indeed represent both these boxes as programs, program 'A' reads the source code and determines if it halts or loops. program 'B' takes the input of program 'A' and does the opposite
Surely if program 'B' loops forever then we know that program 'A's input must halt and likewise, if program 'B' halts then we can assume that program 'A's input must loop infinitely.
The Halting problem isn't about whether or not the program needs to loop, it's about whether or not the program will ever stop looping!
If I give you an infinitely long list to take as input, and you can only see one character at a time as you take it in, you don't know if there's 5 characters left, 1000 characters left, or an infinite amount left.
So it keeps looping and you keep waiting... Are you waiting for a minute? An hour? A year? Or forever?
The issue is that you can never know if the program is going to loop forever or if it will eventually halt and you just need to give it more time.
This is not true for every program, but the Halting problem proves that there must exist some programs out there for which you can never determine if they will halt or loop forever.
The idea with the program determining whether another program will loop or halt is used to prove that the Halting Problem has no solution.
The issue with your scenario arises when the two black boxes are one in the same. For this proof, proving that the Halting problem can be solved sometimes is not good enough (because you did not prove that it can always be solved). A proof by contradiction shows that the Halting problem cannot always be solved.
PROOF:
Let's assume Program A can always know whether program B will halt or loop forever. Let's also assume Program B always does the opposite of what Program A says will happen.
Therefore, no matter what prediction Program A gives about Program B, Program A will ALWAYS be wrong about whether Program B halts or not.
Therefore, you cannot have a Program A such that it always knows whether Program B will halt or not.
This can be an unintuitive proof with how it's setup, but it's true.
If I give you an infinitely long list to take as input, and you can only see one character at a time as you take it in, you don't know if there's 5 characters left, 1000 characters left, or an infinite amount left.
So it keeps looping and you keep waiting... Are you waiting for a minute? An hour? A year? Or forever?
The issue is that you can never know if the program is going to loop forever or if it will eventually halt and you just need to give it more time.
This is not true for every program, but the Halting problem proves that there must exist some programs out there for which you can never determine if they will halt or loop forever.
The idea with the program determining whether another program will loop or halt is used to prove that the Halting Problem has no solution.
The issue with your scenario arises when the two black boxes are one in the same. For this proof, proving that the Halting problem can be solved sometimes is not good enough (because you did not prove that it can always be solved). A proof by contradiction shows that the Halting problem cannot always be solved.
PROOF:
Let's assume Program A can always know whether program B will halt or loop forever. Let's also assume Program B always does the opposite of what Program A says will happen.
Therefore, no matter what prediction Program A gives about Program B, Program A will ALWAYS be wrong about whether Program B halts or not.
Therefore, you cannot have a Program A such that it always knows whether Program B will halt or not.
This can be an unintuitive proof with how it's setup, but it's true.
Last edited on
Topic archived. No new replies allowed.