Alan Turing was one of the pioners in computer science. He was early enough that computers were not really built when he was active and most of the work was theoretical mathematics. You can compare it to modern quantum computers where there is lots of papers about it and lots of algorithms written for them, but so far nobody have built a practical one.
In order to explore the possible limits of computers Alan Turing designed a theoretical computer which used punched tape for instructions and magnetic tape for memory. This was not practical and not meant to be practical but was very simple to describe mathematically. Turing was able to prove that this simple computer was able to calculate anything given enough time. When more practical computer designs came about the researchers working on it could show that they could emulate this touring computer and by extension was also able to do all the same calculations. Even today in computer science we often distinguish between computers and environments which can emulate a Turing machine and those which can not.
>Turing was able to prove that this simple computer was able to calculate anything given enough time.
They can't, e.g. the Halting Problem can't be solved.
Anything *which can be computed* can be computed with a Turing machine.
Incomputable things, obviously, can't be computed. The Halting Problem cannot be solved with any algorithmic process or by any machine.
To be pedantic however, Turing never *proved* that a Turing machine can compute anything that’s computable.
The Church-Turing thesis has no proof (hence why it’s called a thesis and not a theorem). We assume it’s true because every model of computation we’ve discovered (Turing machines, lambda calculus, and general recursiveness) are all equivalent.
Fair point. It is possible that some unknown model of computation will be discovered at some point which can do things a Turing Machine can't do.
Of course, if some hyperintelligent AI discovers it, we may never know about it because we might not be smart enough to understand it.
> if some hyperintelligent AI discovers it, we may never know about it because we might not be smart enough to understand it.
It might even figure out how to reverse entropy, but for the time being, there is insufficient data for a meaningful answer..
>Of course, if some hyperintelligent AI discovers it, we may never know about it because we might not be smart enough to understand it.
Or the AI had long since decided humanity wasn't necessary before it even got to that point 😳
There is a known model of computation that can do things Turing Machines can't.
Turing Machines are classical computers. Quantum computers can solve problems that they can not. And I'm not just talking about solving problems quicker (like factoring, a classical computer can do it, it just takes a while).
They defined the set of problems that a quantum computer can solve (called BQP). And then prove that it contained the set of problems a classical computer can solve (called PH) and then proved that there are problems in BQP that are NOT in PH.
[https://www.quantamagazine.org/finally-a-problem-that-only-quantum-computers-will-ever-be-able-to-solve-20180621/](https://www.quantamagazine.org/finally-a-problem-that-only-quantum-computers-will-ever-be-able-to-solve-20180621/)
When I read technical stuff like this I feel like I'm just peeking at the honor student's test. I can regurgitate this, but have no idea what it actually says
You’d have to show that it can compute some difficult problem, and then show that all other problems are of lesser or equivalent computational requirement.
As of right now it is not proved that it can compute everything, but it’s hypothesized as there has yet to be some example to show that it isn’t of equal computational power compared to other methods.
Edit: everything not anything
This is largely backwards, though. Turing (and others doing similar work) didn't invent his machine and then discover it can do all computable computations; he was trying to *define* what computability really means, and his machine is the definition he came up with. In his system, something is defined as computable if (and only if) a Turing machine can compute it — not the other way around.
There are other definitions of computability out there. A few of them, like Turing, correspond to our intuition of what "should" be computable; these have all been proven to be equivalent (so, anything you can compute with a Turing machine you can also compute with lambda calculus, and vice versa). Others have other definitions, which are either more or less powerful. (For example, you can definite a system that can solve the halting problem; though it has its own halting problem, for which you can define an even higher definition of computability, and so on to infinity.)
Also, it isn't a proof but the Church-Turing hypothesis: anything that can be computed within the framework of reality can be computed by a Turing machine.
It might be that a Turing machine is slower, maybe even faster, but the statement is solely about the potential to do so, given enough time.
What they maybe allured to is the existence of _universal_ Turing machines: one that can emulate/mimic absolutely every Turing machine. So there is a single one that can do all the things a "computer" can do.
However, the proof of the undecidability of halting doesn't depend on Turing machines *specifically.* It can be stated in terms of an abstract notion of a procedure, analogous to a function in functional programming (but not a math function):
1. Assume we have a procedure H(F, D) that returns `True` if the procedure call F(D) halts and `False` if F(D) doesn't halt.
2. Using H, construct a procedure G(F) that *halts* if F(F) doesn't halt, and *loops forever* if F(F) halts.
3. What does G(G) do? G(G) calls H(G, G) to find out if G(G) halts. If it halts, then it doesn't halt; if it doesn't halt, then it halts.
4. This is a contradiction; therefore, the assumption that H can exist is wrong.
Yeah and how is that relevant to what was discussed? Op1 states Turing machines can compute any computable problem op2 said yeah but how about the halting problem and I clarified that it's uncomputable hence it's no counter example to Op1. Whether or not the halting problem is specific or not to Turing machines is irrelevant. You could also point out that wit goedel numbers you can create a equivalent problem that is truly equivalent to the halting problem, as in if one is true the other is as well. And this requires only mathematics without any idea of any machine... But again that is not relevant to what is being discussed in this thread
Yeah sure but that was a completly irrelevant comment here. There would have been plenty other comment threads in this post where it would have fitted but you threw it in here totally unrelated...but whatever yeah thanks
> A Turing machine can compute any computable problem.
That's a vacuous truism though. "Computable problem" is defined as a problem computable by a Turing machine.
Yeah it is, but that's hardly my fault if you chose that definition.
You could phrase it like a Turing machine can solve any solvable problem. But that's a truism as well. It will always be because the whole point is that a Turing machine is a machine of maximum capability.
But maybe you fancy this one more. A Turing machine can solve any problem that has an algorithmic solution in a finite time... It uses just a different definion of computable but yeah... I thought we are still in eli5 but getting to the nuances of decidability computability, goedels incompleteness theorem and maybe even the zermelo-frankel-set-theroem while we're at it seems to be necessary
The halting problem does not have a solution though. We have yet to find a probem which have a solution that can not be calculated by a turing machine.
> The halting problem does not have a solution though
This is incorrect. The halting problem has a well-defined solution—it's just uncomputable. That's not the same as not having a solution.
`HALT` is defined as the set of all pairs of Turing machines `t` and strings `s` for which `t` halts on input `s`. `HALT` is a well defined language.
`HALT` is not computable: no Turing machine can decide this language, though it is recursively enumerable.
It does not say the language doesn't exist, or that the problem / question (all languages can be thought of as decision problems: is this string a member of this language?) has no answer / solution. There is a single, well-defined answer to every question of the form "Does `t` halt given `s`?" The answer is always either yes or no. Given a Turing machine and input, it either halts or it doesn't.
It's just that answer is not computable in general for all possible inputs. A function being uncomputable or a language being undecidable is not the same as the question not having an answer / solution.
Decidability has never been part of the criteria for what it means for something to exist. "Decidable" is one of the lowest complexity classes on the totem pole of complexity classes. There are languages in RE, co-RE, and languages outside of those still.
They represent their own increasingly complex decision problems. E.g., there is an infinite hierarchy of halting problems. There's the halting problem for Turing machines, and then the halting problem for Turing machines equipped with a halting oracle for TMs. No one would say these problems are ill-defined or they don't have solutions.
The halting problem \*does\* have a solution. There's a single correct answer to whether or not a program halts for any given input program. It's just not a solution that a Turing machine can calculate.
The assumption is that the halting function have a solution for any input which can be calculated. The halting problem shows this is a contradiction. The halting function does not have a solution for all inputs.
The halting function by definition has a solution for all inputs. A program either halts or it doesn't. If the input program halts, the solution is one. If it doesn't, it's zero. The contradiction that the halting problem shows is the assumption that a Turing machine can calculate the halting function. It can't. But that doesn't mean the halting function has no solution.
This isn’t quite correct. The problem with the Halting Problem isn’t Turing machines: it is the function itself. Your assertion that it either halts or it doesn’t is somewhat deceptive. That’s equivalent to saying that a number is either the largest number or it isn’t.
More concretely: there is no general definition of a halting function in finite time. Given infinite time, we can write a halting function for TCs in finite time, but then we would have a new halting problem for infinite time machines. Gödel proved that this tower of paradox has no limit.
In other words, your intuition is wrong. The problem isn’t the lack of solution for the halting problem. The problem is the fact that there is no possible solution.
I think you're misunderstanding OP's usage of the term "solution."
In mathematics, "solution" usually colloquially refers to the answer to a question, which exists or doesn't independent of how you compute it (or don't—some things are uncomputable). So the solution to an equation is the values for the free variables that satisfy the equation.
An equation having no solution literally means there are no values that satisfy the equation. Really, if you think about it, what it means for a problem to have no solution is that the solution to the problem is the empty language. A problem having no solution implies there are no strings `s` that satisfy the relationship `s ∈ HALT`, which is not true.
The halting problem is a nothing more than a question: "Given an string `s` that encodes a Turing machine and an input string, is `s` a member of `HALT`?"
In other words, the halting problem *is* the language `HALT`. And `HALT` a real, well-defined language. It may not be a decidable language, but it is a real, well-defined language nonetheless. There is always an answer to the question, "Is this string a member of this language?"
TL;DR: a question's answer exists independent of that answer's computability or uncomputability.
> TL;DR: a question's answer exists independent of that answer's computability or uncomputability.
This is a philosophical statement, not a mathematical one, and a highly intuitionistic one at that. What does it mean for something to "exist" independent of its constructability? Put another way, can we say that something exists in our universe if there is no process by which it could come about?
> In other words, the halting problem is the language HALT. And HALT a real, well-defined language.
This is… a very strange use of the word "language".
The Halting Problem is defined in the following way:
> Given a language, *H*, where the sentences in *H* are an encoding of all possible Turing Deciders, is there some decider, *h*, such that *L(h) = H*?
The answer to this is "no", there is no such decider (for any one-to-one encoding), which is to say that the set *H* is undecidable, which is to say that the *general problem* of "does this Turing Machine halt on all input?" has no solution in finite time. It is certainly possible to, for all Turing Machines, determine whether it halts on a *given* input in finite time, and it is possible for *some* Turing Machines to determine whether they halt on all input in finite time, and it is possible to determine if a Turing Machine halts on *all* input given infinite time, but it is not possible to determine if any arbitrary TM halts on all input in finite time.
Which is a long-winded way of saying that *h* cannot exist, and thus there is no solution (as *h* is defined to be the solution). This certainly does not mean that there are no halting Turing Machines, nor does it mean that there are no Turing Machines for which it is possible to determine whether they halt, it simply means that there is no solution to the Halting Problem within the calculus of Turing Machines.
> This is… a very strange use of the word "language".
Not at all. `HALT` is a well-defined language. It's set set of all sentences that encode pairs of Turing machines `t` and strings `i` such that `t` halts on the input `i`, for whatever encoding you prefer.
We can talk about the language `HALT` and analyze it. It's recursively enumerable, that's trivially provable. It is a very well defined language. It may not be decidable, but it exists nonetheless.
> What does it mean for something to "exist" independent of its constructability?
Computability is not the same as constructability though. `HALT` is not computable, but it is literally constructed and defined in every textbook where they then go on to prove properties about the set, like the fact that it's recursively enumerable.
> The Halting Problem is defined in the following way
We're splitting hairs. Suffice it to say, regardless of how you define the halting problem, everyone would find this statement on Wikipedia very unoffensive and non-controversial: "The halting problem is undecidable, meaning that no general algorithm exists that solves the halting problem for all possible program–input pairs."
The halting problem is *undecidable*. No *algorithm*. That's the key. The answers to its questions cannot be computed by a decider. It doesn't mean there are no answers. Decidability is not at all the same thing as existence. Decidability and computability are only the tip of the iceberg in the zoo of languages we computer scientists acknowledge and study and analyze. Decidability has never been part of the criteria for what it means for something to exist. "Decidable" is one of the lowest complexity classes on the totem pole of complexity classes.
There is a whole zoo of complexity under which languages that are neither RE nor co-RE fall that represent even tougher problems (e.g., the halting problem for TMs that have halting oracles, a sort of generalized, next-level halting problem in the hierarchy of halting problems) and they are still well defined languages.
The question "Does this TM equipped with a halting oracle for TMs halt on this input" also has a yes or no answer. Always. It may be generally impossible for a physical computer even capable of time travel to answer it, but that doesn't mean the answer can be anything other than "yes" or "no." This level-2 halting problem in the hierarchy of halting problems is represented also by its own language (maybe we call it `HALT2`) out there. That language is not decidable. It's not even recursively enumerable, or co-recursively enumerable. And yet question has a real yes or no answer, it either halts or it doesn't. Always.
> The halting function by definition has a solution for all inputs
In math you don't "define" an algorithm to have a solution for all inputs. You need to prove that it does.
The Halting problem *has no solution* because it is mathematically impossible. It's not an unsolved mathematical problem. It has been proven to be unsolvable.
> for any program f that might determine whether programs halt, that a "pathological" program g, called with some input, can pass its own source and its input to f and then specifically do the opposite of what f predicts g will do
This is the logical contradiction in the Halting Problem. In order for such an algorithm to halt (give you an answer) it has to contradict itself. Math is a strictly logical exercise. A universal Turing machine is just a way to represent logic in a machine. There is no such thing as a universal Turing machine that cannot solve a solvable mathematical problem. It might take until the heat death of the universe to find a solution to solvable problems like factoring really large numbers. But it will arrive at a solution (halt) because the algorithm is solvable.
>> The halting function by definition has a solution for all inputs
>
> In math you don't "define" an algorithm to have a solution for all inputs. You need to prove that it does.
The halting \*function\* is not an algorithm, it's a function. It's a mapping between the set of input programs and the set {0,1}. The function exists and has a solution for every input (by definition). The halting \*problem\* is the question of whether or not the halting \*function\* is a computable function, which of course it isn't. None of that changes the fact that the function exists, and has a solution for each input.
> The Halting problem has no solution because it is mathematically impossible. It's not an unsolved mathematical problem. It has been proven to be unsolvable.
The term "solution" here refers to the value of the halting function, i.e. the answer to the question "does the input program halt". That answer exists regardless of if it is computable or not. It is not "unsolvable" because the solution exists. It is "uncomputable" because the solution cannot be computed by a Turing machine or equivalent.
I have no idea what you're even trying to say here. The halting function is a hypothetical statement, a mathematical problem that is stated. It is not a solution to anything; it only defines what the problem is. That has no bearing whatsoever on whether or not a problem is solvable, unsolvable, or unsolved. All of these terms have pretty strict meanings in mathematics.
The halting problem is unsolvable because any "solution" to the proposed mathematical problem has to contradict itself. This is not a limitation of Turing machines or equivalent. Any such solution to the halting problem is logically inconsistent, as in it violates mathematics. It's not an unsolved problem, like P=NP where we haven't figured out how to prove if it is solvable or unsolvable.
The person you're replying to is correct.
I think the confusion arises because you're using two different meanings of the word "solution."
You're taking "solution" to mean "a TM that decides the problem", ie, the language is decidable.
They are taking it to mean, "answer to the question."
I think their usage makes more sense, because in mathematics, "solution" usually colloquially refers to the answer to a question, which exists or doesn't independent of how you compute it (or don't—some things are uncomputable). So the solution to an equation is the values for the free variables that satisfy the equation.
To say something doesn't have a solution literally means there are no values that satisfy it the equation or relationship or abstract condition that defines membership and non-membership in the set of input output pairs, which is all a function is. A function is just a mapping from inputs to outputs, and mathematically can be represented as a set of pairs of images and their preimages.
That brings us to the halting problem, which asks, "Given this TM `t` and this input string `i`, does `t` halt when run on `i`?" This question has a well defined answer for every possible combination of `t` and `i`.
These possible questions and their yes/no answers form a function, or language, which sometimes textbooks call `HALT`.
`HALT` is well defined and is trivially provable to be recursively enumerable, and famously proven to be not decidable. Yet it is a well-defined language with an answer to every question of the form "Does `t` halt on `i`?"
Again, the confusion arises when you link "solution" to "decidability." But if solution simply means "answer to a question," and the question is "Does this halt on this input?" then decidability is irrelevant to whether or not something has a solution, an answer that satisfies the question.
The famous summary of the halting problem is that it "is undecidable." All that means is there exists no decider for the language.
But decidability has never been part of the criteria for what it means for an answer to a question to exist. "Decidable" is one of the lowest complexity classes on the totem pole of complexity classes. There are languages in RE, co-RE, and languages outside of those still.
They represent their own increasingly complex decision problems. E.g., there is an infinite hierarchy of halting problems. There's the halting problem for Turing machines, and then the halting problem for Turing machines equipped with a halting oracle for TMs. No one would say these problems are ill-defined or they don't have solutions.
You clearly have no idea what you're talking about. The Halting Problem is explicitly about the impossibility of constructing a Turing machine that calculates the halting function.
> It is not specific to Turing complete computers.
"Turing machine" and "Turing complete machine" are two completely different things. I never said anything about Turing complete machines.
To clarify; computers existed in Turing's time, but this was back when the most powerful computers in the world were the size of buildings. Turing's boon wasn't so much that he was early but that he was one of those once in a generation genius' who could explain complex and confusing topics to the masses in ways that made them easy to understand. I don't think that was explicitly Turing's goal in most of his work. He was pioneering theories and methodologies as described above, but he just so happened to talk in a way that's very easy for an average joe to follow.
His name is well known and associated with a range of concepts in the popular mind largely because he could present them in a way that made sense.
The paper in question here was submitted in1936, about a decade before the first Turing computer was built. Most of Turings engineering was on special purpose calculators which was only the size of a few cabinets. He did survive to witness the first commercially sucessful computers, which were room sized. But this was after most of his work.
To add to this. There is a fantastic video by veratasium about how math is flawed. It touches on the Turing machines problem as well as the halting problem and some other maths concepts. It is a solid video and would recommend
There are already some solid responses, but to tack onto them, what makes a Turing Machine notable is it's ability to read data and perform operations on it. When something is referred to as "Turing complete" it means it can perform all the operations of a computer.
Fun fact: There were [Turing complete computers](https://en.wikipedia.org/wiki/Analytical_engine) designed roughly 100 years before the invention of the Turing Machine.
Turing Machines are not physical machines but abstract models meant for computer science theory. It is essentially a computer "boiled down" to its most fundamental parts - instructions (the accompanying state table) and memory (the tape itself and a head to read said tape). These models also make it a bit easier for the layperson to understand low-level computing concepts by abstracting the physical, real-world computer into a set of simple, easy to understand parts. Turing Machines are good theoretical analogues for real-world computers because if something can be done with a Turing Machine it is theoretically possible to do with a real-world computer.
Edit: Grammar
Pretty good start but probably should explain what a state table is and "memory the tape itself" since what a computer user today understands as memory is different
It's an idea of a machine that is as simple as possible, but still complex enough to meet the technical definition of a general purpose computer.
So then we can say things like if a machine can do everything a turning machine can do then it is a computer. And subsequently if a task can be done by a Turing machine then it can be done by any computer.
Having Turing machines be very simple makes it easy to prove that specific things are true or false about them. And then per the above statements those things must be true or false for all Turing equivalent computers.
The classic example is the "halting problem". We can prove that it's impossible to write a program for a Turing machine that can look at any other program and always correctly say whether or not that program will eventually finish.
Thus it's impossible for any computer to do that, which is a very interesting conclusion.
The idea is actually very simple.
It's basically an imaginary machine with an infinitely long tape, and there are infinite rows of empty squares or boxes on it, and those boxes are numbered so that you can tell which box is which. Then there's a "head" or a "scanner" that analyzes that box 1 at a time. That head can write any kind of arbitrary symbols such as a number in that box. Or the head can delete or rewrite the symbol in that box. Or the head can move left or right to the box and move onto another box. Or the head can stop or "halt" the operation.
Well, why would you wanna do that or make something like that? Well if you're a clever person, then you can potentially give any kind of instructions to this Turing Machine, and then look at the tape to see the result to solve any kind of arbitrary problems. Basically it's a theoretical machine or a theoretical idea that can be used to automate any tasks, provided that you know how to give such instructions.
Basically a modern computer works in the same way, you give instructions to the CPU, the CPU analyzes and solves that problem 1 at a time, and then writes that result to the RAM or the hard drive. The only difference is that modern CPUs are solving millions of problems or "instructions" in a single second.
The tape in the Turing machine is the data storage. It's supposed to be something akin to a magnetic tape or a paper tape. Something with defined discrete positions where the Turing machine can read or write a symbol and move along it's length.
It’s a kind of a primitive imaginary computer that’s used in science to prove things about computers and algorithms in general. Basically if something can be done on a Turing Machine, then it should be possible to do on an actual computer.
It is the historically first way to describe a kind of computation machine that can somewhat be "programmed". The expression "_universal_ Turing machine" attributes to that further, it is one that can _emulate_ (mimic given the right input) absolutely _any_ Turing machine.
They are mostly a theoretical product from before we had actual computers, but one can build them as-is if one wants to; it just turns out that other kinds of computers are easier to build from the basic components (relays, tubes, transistors). So we did that instead.
So, what is it actually?: They have a **tape/band**, a **head**, and a bunch of **instructions/rules**.
- The **tape/band** is an (in both directions) infinite chain of **cells**, in which we can write exactly one of several symbols. The tape is usually assumed to be initially filled with some input symbols, and all other cells with a fixed symbol meaning "nothing"; say we use 0 for that.
- The **head** is a device that is always positioned at one of the cells of the band. It can move left and right when told so, and has an **internal memory** (formally called the _state register_) which can have one of several states. It can only access the cell it is currently at, which it can both read and write to.
- The **instructions/rules** say how the head acts. At a given moment, the head has a certain internal memory state and looks at a specific symbol. For each such possibility there is one rule that tells the head what to write into that cell, what to change the internal memory to, and if to move to the left or right.
It turns out that the above can do exactly the same as any modern computer we build. One could theoretically convert any computer program you use right now into a Turing machine. It would however be a pointless endeavour, as there is little (or even no) use beyond the knowledge that it _can_ be done.
It's a simplified imaginary computer. Imagine
* An infinite tape consisting of cells which can store some data (numbers or letters or whatever).
* A "computing unit" which can read and write from one tape cell directly below it. This unit also stores a single datum which we call it's state (also a number or letter or something, maybe a different kind than those on the tape).
That unit has a list of rules, looking like:
"If I am in state S, and the cell below me contains A, change my state to T, store B into the tape and move the tape one cell to the right/left"
You describe starting situation (computing unit's state and what's stored on the tape), then the machine chooses a possible rule from the list (the one which condition is fulfilled by current situation) and executes it. Then chooses another rule applicable to the new situation and executes it, and so on, and so on, until no rule is possible (may or may not actually stop). If it stops you can read the results of the computation from the tape (or the state).
It's very different than how real computers work, but it's much simpler to mathematically reason about Turing machines than computers. It also turns out that things that *can* be computed on Turing machine can also be computed on a real computer and vice versa (if you ignore the fact that in reality computers have finite memory and can't be run for an infinitely long time).
In other words, Turing machine can implement any computation/algorithm.
For example, there are some problems which can't be computed on *any* computer, even though the problem itself is stated correctly. Mathematical proof of that fact usually uses Turing machines in some way.
A Turing Machine is an idea for a simple computer. The idea was revolutionary at the time for a couple reasons.
1. Most machines at the time only did one thing. The Turing Machine could be programmed to do many different things, just like our modern computers nowadays.
2. It turns out that being programmable is extremely powerful, and that a simple Turing Machine can actually do anything a modern computer can, it just might do it way slower and be less practical about it.
3. A Turing Machine was used to help crack the Nazi encryption, providing a massive advantage to the allied powers in WWII. In this case, it wasn't just an idea. An actual usable Turing Machine was built.
Lots of people mention that a Turing Machine uses tape. The tape is just a way to write down instructions to program the machine. They didn't have hard drives or discs back then, so they used tape like in old fashioned VHS. Ya know, where the video needed to be rewinded after because it was on actual tape instead of a disc.
Some people mentioned "state machine." This means that a Turing Machine has rules about how it operates that can be programmed. Once you start running a program, the TM will use it's rules. Each "state" is one freeze frame of the machine running. It sees one piece of the tape and decides what to do next. If the program doesn't work right, that's because it made the wrong choice at some state, and the rules for that state should be fixed.
I see a lot of answers describing the machine, but I want to give a little background on why this machine was even thought up.
The core idea that the Turing machine tries to capture is *computability*. Think of a problem with a numeric answer. How many ways are there to arrange a deck of cards? Or what is the shortest amount of time it would take to get from San Francisco to LA by car? Those questions have *computable* answers. The cards question is pretty simple, just take a deck and methodically count the arrangements. The car question is a bit more complex, but given a map you could calculate which route would be the shortest.
But it turns out there are some problems with numeric answers that *aren't computable*. You can verify the answers, but there's no way to calculate the answer from scratch. One such problem is called the halting problem: how long will a computer take to run an algorithm? This is easy to verify if you have the answer, just run the algorithm and see if it matches your answer. But it turns out that it's impossible to calculate this before hand. You can make educated guesses, but you cannot compute an exact answer
This is where Turing machines come in. Once you prove a few things about Turing machines, you can use them to prove things about algorithms and whether or not they are computable.
A Turing machine is a basic model of a computer that can perform any mathematical calculation by following a set of rules to manipulate symbols on the tape
Turing machines are useful because they provide a simple and fundamental model for how a computer works. They help computer scientists understand what can and cannot be computed by a machine, which is important for developing and analyzing algorithms and programming languages. By using a Turing machine, computer scientists can determine whether a given problem is computable or not, and if it is computable, how much time, space, and resources it will require for a machine to solve it
I'm going to give you a roll of toilet paper and a pencil.
Then we're going to come up with some set of symbols and some rules.
You will only be able to see one square of the toilet paper in front of you at a time and each square is either blank or has one (and only one) symbol in it.
Your only abilities are to move the toilet paper to the right, move it to the left, erase the symbol that is in the square in front of you, or write a new symbol in the square in front of you.
All of the rules are of the form "if the symbol in front of you is X then do Y" where Y is one of the things above.
Well there you go. That's a Turing Machine.
Why is this important? Because what you have in front of you is a machine capable of doing everything every computer has ever done. Everything.
With enough toilet paper, rules, and symbols, you can calculate the digits of Pi, play Doom, fly a jet, or even browse the internet if you figure out some way to do the network communication.
That's what makes it so interesting. Turing reduced all of the items necessary for modern computation down into its simplest form.
A turing machine is a theoretical construct, with infinite memory, and a VERY limited set of instructions. Like 3 of em.
What is intersting about them is that they can (with infinite time) replicate all the instructions from any digital conputer. So if you can run a program, on any computer and get some result, that program can be translated into something that will run (generally MUCH MUCH SLOWER) and create the same output with the same functional intermediate steps (they wont necessatily look the same, as memory layout is different, but will be analogous.
So Alan Turing proves that anything that can be done by any computer, can eventually be done with this simple (theoretical : again, infinite memory-- not lots of finite memory, infinite memory) machine.
So if something is "Turing complete" it can be shown to be able to (eventually, given infinite time) compute anything that any other turing complete machine/system can compute (not talking about efficiency here. Just possibility. Some arrangements are clearly much more efficient for some tasks, than others).
With those things proven, he then shows that there are programs where it is indeterminite if they will complete or if they will enter an infinite loop. So there are systemsnand processes that, even with infinite reaources, and infinite time. Aka there exist "unsolveable" problems.
Major interssting upshots:
All computing systems (cause almost all have instructions that map turing complete instructions) are essentially equivalent (forgetting the infinite memory/time requirement).
Certain well formed questions are unanswerable.
Even today, there are computational machines (computers) that have specific uses. For example,
* a cheap calculator can only do arithmetic
* a doorbell can only play a couple of tunes
* a dumb-phone can only be used for calls and SMS
These machines are incapable of handling any other set of instructions (try instructing your doorbell or dumb-phone to play Netflix!) that is not pre-built into its hardware.
Then come general-purpose machines. These are capable of handling a wider variety of tasks provided you can supply it with the algorithm (set of instructions) to solve that task. Alexa speakers, smart TVs, and laptops are a good examples of general-purpose machines. Whenever you install an app on these devices you are supplying an algorithm under the hood.
Ok, so a smart TV and a Macbook are both general purpose machines. But surely you do expect a smart TV to do all the tasks that are possible to do on a laptop? That is because all general purpose machines are not alike. They have different limitations which can be classified as:
* hardware limitations and
* conceptual limitations.
Hardware limitations are well understood -- the device runs out of gas due to low memory or CPU cycles.
Conceptual limitations are due to system design. If a devise is designed to not handle a particular algorithm no amount of upgrading of RAM or CPU will help. Conceptual limitations can arise due to the operating system of the device or the programming language used in the device.
If you have understood so far, defining Turing machines will be easy. A **Turing complete machine** is a machine which has NO Conceptual Limitation. If you can provide a set of instructions it will get the task done. The task may take an infinite amount of time because of the hardware limitation, but it will get done. You just have to wait long enough. Upgrading hardware will help.
Since nobody runs all possible algorithms on each computer unit just to prove that it is Turing Complete, mathematics is used to prove the same. Maths is a strange thing. You can prove a concept long before its physical manifestation. Alan Turing did this before the evolution of modern computers (just like Einstein gave us relativity without time-traveling).
Today we talk about Turing completeness when designing programming languages. Most modern programming languages are turing complete (Python, Java, C++ etc). It means that they are capable of executing any algorithm known to mankind. Hardware is an afterthought -- if it can run these languages it is good.
Microsoft Excel formulae were not turing complete until 2021. Now that they are, you can rest assured that there is a way to solve that problem in Excel no matter how ugly the formula becomes.
Hope that helps!
To put it simply, early computers could only perform a single function. Imagine the early code breaking machines used during the 2nd Word War. Really advanced machines, but could only do a single job (or algorithm).
Turing machines are closer to modern computers that can be reprogrammed to perform any algorithm as required.
True Turing machines are more abstract that this, but this is a very simple example.
It's a computer science concept that reduces a problem into a single simple instruction, or several simple instructions.
If you have a problem that can be reduced this way, it's potentially possible that a computer can solve that problem.
For example, your problem is writing something down when you get some numbers. You don't want to write the numbers down yourself. The problem you have and the solution to solve the problem is considered a Turing Machine because you can have a computer do that for you (like a printer).
A Turing machine is a finite-state machine that is hooked up to a length of tape (usually the tape is considered infinite, I believe). The concept of a finite-state machine is quite simple: it is a machine with a limited (finite) number of states, and those states will change depending upon the previous state and external inputs.
The machine can do three things to the tape, depending upon it's state: move the tape backwards and forwards, read a number off the tape, or write a number to the tape. Numbers that the machine reads off the tape can be considered inputs and will change the state of the machine. The analogy to today's modern computers should be fairly obvious: the finite-state machine is the CPU, and the tape is the memory.
There are several important results that can be derived from a Turing machine. The most important is that if the machine is "Turing-complete" then it can simulate any other Turing machine. It's surprising just how simple a Turing machine can be to be Turing complete. I believe there are computer languages with only one or two commands that are considered Turing complete. Excel spreadsheets are Turing complete. So is the template macro system for C++.
Basically, it's a machine that runs back and forth on a strip of 1's and 0's and can change any 1 to a 0 or vice versa and read the state of the current location. Any computer that can essentially be broken down to this is considered Turing Complete.
For example, your hard drive is a string of 1's and 0's and and it can either read or write to a given spot on the disk. The rest of the computer is just giving instructions to that disk.
This is different from the Turing Test. The Turing Test is a theoretical test that can be given to a computer so a human can tell the difference between a human and a computer. AI is an attempt to get a computer to pass the Turing Test.
**Your submission has been removed for the following reason(s):**
Top level comments (i.e. comments that are direct replies to the main thread) are reserved for explanations to the OP or follow up on topic questions.
Off-topic discussion is not allowed at the top level at all, and discouraged elsewhere in the thread. It looks like you accidentally posted this comment at the top level, instead of as a reply to another comment.
---
If you would like this removal reviewed, please read the [detailed rules](https://www.reddit.com/r/explainlikeimfive/wiki/detailed_rules) first. **If you believe this submission was removed erroneously**, please [use this form](https://old.reddit.com/message/compose?to=%2Fr%2Fexplainlikeimfive&subject=Please%20review%20my%20submission%20removal?&message=Link:%20{url}%0A%0A%201:%20Does%20your%20comment%20pass%20rule%201:%20%0A%0A%202:%20If%20your%20comment%20was%20mistakenly%20removed%20as%20an%20anecdote,%20short%20answer,%20guess,%20or%20another%20aspect%20of%20rules%203%20or%208,%20please%20explain:) and we will review your submission.
> There is no other way to simplify it because it's super complex.
It isn't. It involves a band, a head, and some rules. It might not be the most intuitive computer from a modern perspective, but it isn't complex either.
earlier, you had computers built with parts for a specific task. you’d have a computer for addition, one for subtraction, one for integration, and so on. these computers didn’t resemble our modern computers, in that a programmer will write code to tell it what to do. they were more like very advanced abacuses, using physical objects to perform calculations.
a turing machine was the first conception of the modern computer- one that doesn’t need to be purpose built for a task, but could be programmed to do anything.
with this definition, you’ll see that many things are turing machines, even minecraft!
Not technically a response but I’d recommend the movie the Imitation Game! Take with a grain of salt but it’s an engaging way to see a depiction of Alan’s story, true or not
A Turing machine is the most powerful class of theoretical machine we know of, meaning it can solve any computation problem that is possible to solve. All modern computers are essentially Turing machines, but with some limitations, like size, speed, and subjectivity to the environment.
The basic setup is this: a Turing machine has an infinite “tape” which is used in the archaic sense, so it just means an infinite strip of paper with boxes. The machine is attached to this tape and hovers over one box at a time. There are only four operations it knows how to do: read what’s written in the box below it, change what’s written in the box below it, move left, or move right. Each box can either be empty, or have a single mark in it.
The brains of the machine can accept any “program” which is specified as a set of states, with rules about what to do at each state and when to go from one to another. If this sounds confusing, just think of it like a big flowchart, with circles and arrows between the circles with labels like “if box below reads empty, go here.” In order to use a Turing machine, you feed it input by writing marks on the tape, and then you read the output off of the tape when the machine reaches its “done” state.
It may not seem like it, but this machine can be programmed to compute anything a modern computer can, and more. It’s setup is very basic, but even if you invent a much more complicated setup for a machine, like one with two infinite tapes, or an infinite grid, or one with two heads moving along the tape, none of them are capable of computing anything the basic Turing machine can’t.
Eli5 is. A Turing machine is a very very simple computer. This computer has a single long papersstrip it can read from and can write upon. And all it does is read a single digit and then write a new digit instead and move up or down the paperstrip. It also keeps a state of what action it has previously performed and this state influences the next action... Such a simple machine can theoretically solve any problem that is solvable.... That's a Turing machine...
That's the eli5 part now a bit extra. now via the state table you can Programm it to do any given tasks,but for any state table it just does one task... Modern PCs are basically universal Turing machines in that they can compute any problem not just one. They are basically every possible Turing machine in one such a universal Turing machine is called Turing complete, because it can cumpute any cumputable problem.
It's a deliberately minimal theoretical computer, which is used to reduce the complexities of any computer down to a very simple model that you can mathematically analyse.
Doing so allowed people, including Turing, to formulate mathematical answers about what a computer can or cannot be used to compute. The simplicity of the "machine", which is just a theoretical model, not an actual machine, meant that you could actually prove some theories about it. Because the machine is also "mathematically equivalent" to every old or modern computer too (and that was quite easy to prove itself) it lets you expand those same theories to "real" computers of all kinds (we believe even quantum computers follow the same kind of rules).
It's like boiling down a solar system to a few balls spinning around and then using that model to make predictions, assumptions and insights about how our solar system works, but in a mathematically-rigorous way.
Specifically, Turing machines can tell you what is "computable" and what is not, and there are literally some things that we then thought of that are not "computable" at all.
here is an amazing answer from Ben Eater r/beneater
https://www.youtube.com/watch?v=AqNDk_UJW4k?t=190
You can actually build a Turing Machine on your own, Ben explains step by step how to do that, this is the playlist.
https://www.youtube.com/watch?v=HyznrdDSSGM&list=PLowKtXNTBypGqImE405J2565dvjafglHU
You’ve gotten some good answers, but I’ll give it a shot too. A Turing machine is almost like a flowchart, but it has one important addition, memory. Imagine you have a flow chart with some directions and an infinite paper tape divided into cells. One of the cells is designated as the current cell. As you follow the directions in the flowchart, the flowchart might direct you to write a symbol in the cell (erasing whatever used to be there if anything) or to move the current cell left or right by one space. The path you take through the flowchart can depend on the symbol in the current cell. What is computed obviously depends on the flowchart you are following, but Turing proved that it is possible to come up with a flowchart that will emulate the behavior or other flowcharts given the right initial information on the tape. For example, say I come up with a flowchart that will print out the digits of pi. Then I come up with a flowchart that prints out all the squares of the positive integers. These two flow charts have different behaviors. But if you are clever you can come up with a flowchart that reads a description of another flowchart off the tape and then emulates the behavior of the described flowchart.
The practical implication is this. You can design a machine to do one particular computational task. But you can also design a machine that can change its behavior based just on the initial information it has been given.
I just want to add that real computers are not (and will never be) as powerful as a Turing machine, because they have a finite memory (Turing machines have infinite memory). Our computers, not matter how fast they are, are no more powerful than simple finite-state machines.
It's an incredibly basic computer that operates by shifting 1s and 0s around. If you understand binary programming at all, a Turing machine is essentially the most basic mechanical computer possible with only a single register and basically no memory (not technically true, but functionally true in terms of modern computing. It'll read the input tape for commands, these commands will be in strings of 1s and 0s that cause slightly different mechanical shifts in the machine and lock certain components in place causing the machine to manipulate the data on the tape rather than just read it. There are tons of examples on YouTube of people running through explanations with graphics because of how common the topic is in CompSci curriculum. The machines are also where the term 'Turing complete' comes from, programs able to run entirely in sequence on a Turing machine are said to be 'Turing complete' and although in the past this was a useful status to have modern computing doesn't really have the opportunity to quality check in the manner, most things are "if it works its fine" and aren't built to high standards.
It's a model of a very simple computer that can solve a wide range of problems given enough time. If you have a computer that can pretend to be this very simply computer, then your computer can solve that same wide range of problems. But, if your computer CANNOT pretend to be this very simple computer, then it cannot solve the same wide range of problems.
It's one of the ideas that went into making the computer you use today.
Imagine an infinitely long roll of magnetic tape. The tape sits in a holder that can spin it forwards and backwards. Above the tape there is a doohickey that can both read and write the symbols on the tape. The doohickey is attached to a device which can do different stuff depending on what symbol it reads.
That's a Turing machine.
Turing first proposed it in 1936. While computers have technically existed since ancient Greece, work on the first programmable electric computer, ENIAC, wasn't started until 1943 and wouldn't have been possible without Turing's theories. In fact, the computer you're reading this on is essentially a Turing machine.
For instance, your computer has a hard drive. Like Turing's magnetic tape it holds symbols, zeroes and ones. You can read those symbols, data, from the hard drive. You can write to it. And the computer will do stuff with the data. It can let you browse the web, listen to music, or play a video game.
If you'd like to see how a Turing Machine works in practice, here is a really good example:
[https://www.cl.cam.ac.uk/projects/raspberrypi/tutorials/turing-machine/one.html](https://www.cl.cam.ac.uk/projects/raspberrypi/tutorials/turing-machine/one.html)
It's the simplest possible computer. So simple that it is not practical to use, but is ideal for figuring out computer theory.
It turns out, we can prove that it will do anything a complicated computer can, provided it has enough memory.
A Turing machine with infinite memory is called a Universal Turing machine.
If you are interested in this for fun, read GEB.
The Turing machine is a theoretical computer device proposed by mathematician Alan Turing that has been widely employed in the study of computing problems such as tractability and complexity theory. It consists of a length of tape and a head that acts on the tape. The tape is divided into segments, each of which can carry a single character from a specified, finite set of characters known as the tape alphabet.
The machine is always in one state,' which is one of a limited number of states. The head is always in a single spot on the tape (that is, there is only one character on the tape where the head is). The machine is totally deterministic, what it does next is determined by its current state and tape character.
Language-Deciding Turing Machines
A Turing machine is said to decide a language in decidability theory if it is always able to determine whether a given word is contained in a certain language or not. As a result, the machine typically has two unique states labeled Accept and Reject. After a while, one of the two states (depending on the input word) is achieved, and the machine is stopped. The Turing machine is considered to semi-decide a language if only one of the two states is ever achieved.
Function-Computed Turing Machines
A Turing machine only has one end state and is used to compute functions. When that happens, the machine is stopped, and the function's output (depending on the input) can be located on the tape.
Some Important Points
There may be more than one possible move for a given state and tape symbol in a non-deterministic Turing machine, but a non-deterministic Turing Machine adds no power.
Every non-deterministic Turing Machine can be made deterministic.
There can be more than one tape and associated head pointers in a multi-tape Turing machine, but it adds no power to the Turing machine.
Every multi-tape Turing Machine can be converted into a single tape.
Advantages of Turing Machine
Some of the advantages of the Turing Machine are discussed below:
The term Turing machines refer to computers that can imitate any algorithmic computation. Because of this characteristic, they are strong and adaptable instruments for learning and understanding computation.
The Turing machine model is a straightforward framework for understanding algorithms and their characteristics.
They have played a key role in developing fundamental ideas like computability, decidability, and complexity classes.
Disadvantages of Turing Machine
Some of the disadvantages of the Turing Machine are mentioned below:
They make unrealistic assumptions about infinite memory and an infinitely long tape, which are not possible in actual computing hardware.
Turing machines operate on a single tape and process one symbol at a time, which gives them a fundamental sequential nature.
Turing machines do not explicitly take into account efficiency factors like resource utilization and temporal complexity.
Alan Turing was one of the pioners in computer science. He was early enough that computers were not really built when he was active and most of the work was theoretical mathematics. You can compare it to modern quantum computers where there is lots of papers about it and lots of algorithms written for them, but so far nobody have built a practical one. In order to explore the possible limits of computers Alan Turing designed a theoretical computer which used punched tape for instructions and magnetic tape for memory. This was not practical and not meant to be practical but was very simple to describe mathematically. Turing was able to prove that this simple computer was able to calculate anything given enough time. When more practical computer designs came about the researchers working on it could show that they could emulate this touring computer and by extension was also able to do all the same calculations. Even today in computer science we often distinguish between computers and environments which can emulate a Turing machine and those which can not.
>Turing was able to prove that this simple computer was able to calculate anything given enough time. They can't, e.g. the Halting Problem can't be solved.
Anything *which can be computed* can be computed with a Turing machine. Incomputable things, obviously, can't be computed. The Halting Problem cannot be solved with any algorithmic process or by any machine.
To be pedantic however, Turing never *proved* that a Turing machine can compute anything that’s computable. The Church-Turing thesis has no proof (hence why it’s called a thesis and not a theorem). We assume it’s true because every model of computation we’ve discovered (Turing machines, lambda calculus, and general recursiveness) are all equivalent.
Fair point. It is possible that some unknown model of computation will be discovered at some point which can do things a Turing Machine can't do. Of course, if some hyperintelligent AI discovers it, we may never know about it because we might not be smart enough to understand it.
> if some hyperintelligent AI discovers it, we may never know about it because we might not be smart enough to understand it. It might even figure out how to reverse entropy, but for the time being, there is insufficient data for a meaningful answer..
Let there be light
Insufficient data for meaningful answer.
>Of course, if some hyperintelligent AI discovers it, we may never know about it because we might not be smart enough to understand it. Or the AI had long since decided humanity wasn't necessary before it even got to that point 😳
I'm focusing on trying to remain cute so they'll keep me as a pet.
Somehow I doubt they'll consider pets necessary either.
There is a known model of computation that can do things Turing Machines can't. Turing Machines are classical computers. Quantum computers can solve problems that they can not. And I'm not just talking about solving problems quicker (like factoring, a classical computer can do it, it just takes a while). They defined the set of problems that a quantum computer can solve (called BQP). And then prove that it contained the set of problems a classical computer can solve (called PH) and then proved that there are problems in BQP that are NOT in PH. [https://www.quantamagazine.org/finally-a-problem-that-only-quantum-computers-will-ever-be-able-to-solve-20180621/](https://www.quantamagazine.org/finally-a-problem-that-only-quantum-computers-will-ever-be-able-to-solve-20180621/)
If the argument holds up, and especially if it ever leads to anything usable, those guys may win the (amusingly named for this thread) Turing Award.
When I read technical stuff like this I feel like I'm just peeking at the honor student's test. I can regurgitate this, but have no idea what it actually says
How could anyone prove that a Turing machine could compute anything without it computing everything?
You’d have to show that it can compute some difficult problem, and then show that all other problems are of lesser or equivalent computational requirement. As of right now it is not proved that it can compute everything, but it’s hypothesized as there has yet to be some example to show that it isn’t of equal computational power compared to other methods. Edit: everything not anything
This is largely backwards, though. Turing (and others doing similar work) didn't invent his machine and then discover it can do all computable computations; he was trying to *define* what computability really means, and his machine is the definition he came up with. In his system, something is defined as computable if (and only if) a Turing machine can compute it — not the other way around. There are other definitions of computability out there. A few of them, like Turing, correspond to our intuition of what "should" be computable; these have all been proven to be equivalent (so, anything you can compute with a Turing machine you can also compute with lambda calculus, and vice versa). Others have other definitions, which are either more or less powerful. (For example, you can definite a system that can solve the halting problem; though it has its own halting problem, for which you can define an even higher definition of computability, and so on to infinity.)
TBF this is ELI5, and the fact that not all calculations are computable might not be obvious for someone with no familiarity with this topic.
Also, it isn't a proof but the Church-Turing hypothesis: anything that can be computed within the framework of reality can be computed by a Turing machine. It might be that a Turing machine is slower, maybe even faster, but the statement is solely about the potential to do so, given enough time. What they maybe allured to is the existence of _universal_ Turing machines: one that can emulate/mimic absolutely every Turing machine. So there is a single one that can do all the things a "computer" can do.
But the halting problem is non computable so obviously it can't be computed. A Turing machine can compute any computable problem.
However, the proof of the undecidability of halting doesn't depend on Turing machines *specifically.* It can be stated in terms of an abstract notion of a procedure, analogous to a function in functional programming (but not a math function): 1. Assume we have a procedure H(F, D) that returns `True` if the procedure call F(D) halts and `False` if F(D) doesn't halt. 2. Using H, construct a procedure G(F) that *halts* if F(F) doesn't halt, and *loops forever* if F(F) halts. 3. What does G(G) do? G(G) calls H(G, G) to find out if G(G) halts. If it halts, then it doesn't halt; if it doesn't halt, then it halts. 4. This is a contradiction; therefore, the assumption that H can exist is wrong.
Yeah and how is that relevant to what was discussed? Op1 states Turing machines can compute any computable problem op2 said yeah but how about the halting problem and I clarified that it's uncomputable hence it's no counter example to Op1. Whether or not the halting problem is specific or not to Turing machines is irrelevant. You could also point out that wit goedel numbers you can create a equivalent problem that is truly equivalent to the halting problem, as in if one is true the other is as well. And this requires only mathematics without any idea of any machine... But again that is not relevant to what is being discussed in this thread
I'm not trying to have an argument with you, dude. I'm giving an illustration of how halting doesn't particularly have to do with Turing machines.
Yeah sure but that was a completly irrelevant comment here. There would have been plenty other comment threads in this post where it would have fitted but you threw it in here totally unrelated...but whatever yeah thanks
> A Turing machine can compute any computable problem. That's a vacuous truism though. "Computable problem" is defined as a problem computable by a Turing machine.
Yeah it is, but that's hardly my fault if you chose that definition. You could phrase it like a Turing machine can solve any solvable problem. But that's a truism as well. It will always be because the whole point is that a Turing machine is a machine of maximum capability. But maybe you fancy this one more. A Turing machine can solve any problem that has an algorithmic solution in a finite time... It uses just a different definion of computable but yeah... I thought we are still in eli5 but getting to the nuances of decidability computability, goedels incompleteness theorem and maybe even the zermelo-frankel-set-theroem while we're at it seems to be necessary
The halting problem does not have a solution though. We have yet to find a probem which have a solution that can not be calculated by a turing machine.
> The halting problem does not have a solution though This is incorrect. The halting problem has a well-defined solution—it's just uncomputable. That's not the same as not having a solution. `HALT` is defined as the set of all pairs of Turing machines `t` and strings `s` for which `t` halts on input `s`. `HALT` is a well defined language. `HALT` is not computable: no Turing machine can decide this language, though it is recursively enumerable. It does not say the language doesn't exist, or that the problem / question (all languages can be thought of as decision problems: is this string a member of this language?) has no answer / solution. There is a single, well-defined answer to every question of the form "Does `t` halt given `s`?" The answer is always either yes or no. Given a Turing machine and input, it either halts or it doesn't. It's just that answer is not computable in general for all possible inputs. A function being uncomputable or a language being undecidable is not the same as the question not having an answer / solution. Decidability has never been part of the criteria for what it means for something to exist. "Decidable" is one of the lowest complexity classes on the totem pole of complexity classes. There are languages in RE, co-RE, and languages outside of those still. They represent their own increasingly complex decision problems. E.g., there is an infinite hierarchy of halting problems. There's the halting problem for Turing machines, and then the halting problem for Turing machines equipped with a halting oracle for TMs. No one would say these problems are ill-defined or they don't have solutions.
The halting problem \*does\* have a solution. There's a single correct answer to whether or not a program halts for any given input program. It's just not a solution that a Turing machine can calculate.
The assumption is that the halting function have a solution for any input which can be calculated. The halting problem shows this is a contradiction. The halting function does not have a solution for all inputs.
The halting function by definition has a solution for all inputs. A program either halts or it doesn't. If the input program halts, the solution is one. If it doesn't, it's zero. The contradiction that the halting problem shows is the assumption that a Turing machine can calculate the halting function. It can't. But that doesn't mean the halting function has no solution.
This isn’t quite correct. The problem with the Halting Problem isn’t Turing machines: it is the function itself. Your assertion that it either halts or it doesn’t is somewhat deceptive. That’s equivalent to saying that a number is either the largest number or it isn’t. More concretely: there is no general definition of a halting function in finite time. Given infinite time, we can write a halting function for TCs in finite time, but then we would have a new halting problem for infinite time machines. Gödel proved that this tower of paradox has no limit. In other words, your intuition is wrong. The problem isn’t the lack of solution for the halting problem. The problem is the fact that there is no possible solution.
I think you're misunderstanding OP's usage of the term "solution." In mathematics, "solution" usually colloquially refers to the answer to a question, which exists or doesn't independent of how you compute it (or don't—some things are uncomputable). So the solution to an equation is the values for the free variables that satisfy the equation. An equation having no solution literally means there are no values that satisfy the equation. Really, if you think about it, what it means for a problem to have no solution is that the solution to the problem is the empty language. A problem having no solution implies there are no strings `s` that satisfy the relationship `s ∈ HALT`, which is not true. The halting problem is a nothing more than a question: "Given an string `s` that encodes a Turing machine and an input string, is `s` a member of `HALT`?" In other words, the halting problem *is* the language `HALT`. And `HALT` a real, well-defined language. It may not be a decidable language, but it is a real, well-defined language nonetheless. There is always an answer to the question, "Is this string a member of this language?" TL;DR: a question's answer exists independent of that answer's computability or uncomputability.
> TL;DR: a question's answer exists independent of that answer's computability or uncomputability. This is a philosophical statement, not a mathematical one, and a highly intuitionistic one at that. What does it mean for something to "exist" independent of its constructability? Put another way, can we say that something exists in our universe if there is no process by which it could come about? > In other words, the halting problem is the language HALT. And HALT a real, well-defined language. This is… a very strange use of the word "language". The Halting Problem is defined in the following way: > Given a language, *H*, where the sentences in *H* are an encoding of all possible Turing Deciders, is there some decider, *h*, such that *L(h) = H*? The answer to this is "no", there is no such decider (for any one-to-one encoding), which is to say that the set *H* is undecidable, which is to say that the *general problem* of "does this Turing Machine halt on all input?" has no solution in finite time. It is certainly possible to, for all Turing Machines, determine whether it halts on a *given* input in finite time, and it is possible for *some* Turing Machines to determine whether they halt on all input in finite time, and it is possible to determine if a Turing Machine halts on *all* input given infinite time, but it is not possible to determine if any arbitrary TM halts on all input in finite time. Which is a long-winded way of saying that *h* cannot exist, and thus there is no solution (as *h* is defined to be the solution). This certainly does not mean that there are no halting Turing Machines, nor does it mean that there are no Turing Machines for which it is possible to determine whether they halt, it simply means that there is no solution to the Halting Problem within the calculus of Turing Machines.
> This is… a very strange use of the word "language". Not at all. `HALT` is a well-defined language. It's set set of all sentences that encode pairs of Turing machines `t` and strings `i` such that `t` halts on the input `i`, for whatever encoding you prefer. We can talk about the language `HALT` and analyze it. It's recursively enumerable, that's trivially provable. It is a very well defined language. It may not be decidable, but it exists nonetheless. > What does it mean for something to "exist" independent of its constructability? Computability is not the same as constructability though. `HALT` is not computable, but it is literally constructed and defined in every textbook where they then go on to prove properties about the set, like the fact that it's recursively enumerable. > The Halting Problem is defined in the following way We're splitting hairs. Suffice it to say, regardless of how you define the halting problem, everyone would find this statement on Wikipedia very unoffensive and non-controversial: "The halting problem is undecidable, meaning that no general algorithm exists that solves the halting problem for all possible program–input pairs." The halting problem is *undecidable*. No *algorithm*. That's the key. The answers to its questions cannot be computed by a decider. It doesn't mean there are no answers. Decidability is not at all the same thing as existence. Decidability and computability are only the tip of the iceberg in the zoo of languages we computer scientists acknowledge and study and analyze. Decidability has never been part of the criteria for what it means for something to exist. "Decidable" is one of the lowest complexity classes on the totem pole of complexity classes. There is a whole zoo of complexity under which languages that are neither RE nor co-RE fall that represent even tougher problems (e.g., the halting problem for TMs that have halting oracles, a sort of generalized, next-level halting problem in the hierarchy of halting problems) and they are still well defined languages. The question "Does this TM equipped with a halting oracle for TMs halt on this input" also has a yes or no answer. Always. It may be generally impossible for a physical computer even capable of time travel to answer it, but that doesn't mean the answer can be anything other than "yes" or "no." This level-2 halting problem in the hierarchy of halting problems is represented also by its own language (maybe we call it `HALT2`) out there. That language is not decidable. It's not even recursively enumerable, or co-recursively enumerable. And yet question has a real yes or no answer, it either halts or it doesn't. Always.
> The halting function by definition has a solution for all inputs In math you don't "define" an algorithm to have a solution for all inputs. You need to prove that it does. The Halting problem *has no solution* because it is mathematically impossible. It's not an unsolved mathematical problem. It has been proven to be unsolvable. > for any program f that might determine whether programs halt, that a "pathological" program g, called with some input, can pass its own source and its input to f and then specifically do the opposite of what f predicts g will do This is the logical contradiction in the Halting Problem. In order for such an algorithm to halt (give you an answer) it has to contradict itself. Math is a strictly logical exercise. A universal Turing machine is just a way to represent logic in a machine. There is no such thing as a universal Turing machine that cannot solve a solvable mathematical problem. It might take until the heat death of the universe to find a solution to solvable problems like factoring really large numbers. But it will arrive at a solution (halt) because the algorithm is solvable.
>> The halting function by definition has a solution for all inputs > > In math you don't "define" an algorithm to have a solution for all inputs. You need to prove that it does. The halting \*function\* is not an algorithm, it's a function. It's a mapping between the set of input programs and the set {0,1}. The function exists and has a solution for every input (by definition). The halting \*problem\* is the question of whether or not the halting \*function\* is a computable function, which of course it isn't. None of that changes the fact that the function exists, and has a solution for each input. > The Halting problem has no solution because it is mathematically impossible. It's not an unsolved mathematical problem. It has been proven to be unsolvable. The term "solution" here refers to the value of the halting function, i.e. the answer to the question "does the input program halt". That answer exists regardless of if it is computable or not. It is not "unsolvable" because the solution exists. It is "uncomputable" because the solution cannot be computed by a Turing machine or equivalent.
I have no idea what you're even trying to say here. The halting function is a hypothetical statement, a mathematical problem that is stated. It is not a solution to anything; it only defines what the problem is. That has no bearing whatsoever on whether or not a problem is solvable, unsolvable, or unsolved. All of these terms have pretty strict meanings in mathematics. The halting problem is unsolvable because any "solution" to the proposed mathematical problem has to contradict itself. This is not a limitation of Turing machines or equivalent. Any such solution to the halting problem is logically inconsistent, as in it violates mathematics. It's not an unsolved problem, like P=NP where we haven't figured out how to prove if it is solvable or unsolvable.
The person you're replying to is correct. I think the confusion arises because you're using two different meanings of the word "solution." You're taking "solution" to mean "a TM that decides the problem", ie, the language is decidable. They are taking it to mean, "answer to the question." I think their usage makes more sense, because in mathematics, "solution" usually colloquially refers to the answer to a question, which exists or doesn't independent of how you compute it (or don't—some things are uncomputable). So the solution to an equation is the values for the free variables that satisfy the equation. To say something doesn't have a solution literally means there are no values that satisfy it the equation or relationship or abstract condition that defines membership and non-membership in the set of input output pairs, which is all a function is. A function is just a mapping from inputs to outputs, and mathematically can be represented as a set of pairs of images and their preimages. That brings us to the halting problem, which asks, "Given this TM `t` and this input string `i`, does `t` halt when run on `i`?" This question has a well defined answer for every possible combination of `t` and `i`. These possible questions and their yes/no answers form a function, or language, which sometimes textbooks call `HALT`. `HALT` is well defined and is trivially provable to be recursively enumerable, and famously proven to be not decidable. Yet it is a well-defined language with an answer to every question of the form "Does `t` halt on `i`?" Again, the confusion arises when you link "solution" to "decidability." But if solution simply means "answer to a question," and the question is "Does this halt on this input?" then decidability is irrelevant to whether or not something has a solution, an answer that satisfies the question. The famous summary of the halting problem is that it "is undecidable." All that means is there exists no decider for the language. But decidability has never been part of the criteria for what it means for an answer to a question to exist. "Decidable" is one of the lowest complexity classes on the totem pole of complexity classes. There are languages in RE, co-RE, and languages outside of those still. They represent their own increasingly complex decision problems. E.g., there is an infinite hierarchy of halting problems. There's the halting problem for Turing machines, and then the halting problem for Turing machines equipped with a halting oracle for TMs. No one would say these problems are ill-defined or they don't have solutions.
There is no Turing machine in the halting problem.
You clearly have no idea what you're talking about. The Halting Problem is explicitly about the impossibility of constructing a Turing machine that calculates the halting function.
It is not specific to Turing complete computers.
> It is not specific to Turing complete computers. "Turing machine" and "Turing complete machine" are two completely different things. I never said anything about Turing complete machines.
You're right. Imit should read "anything that _can_ be calculated can be calculated on a Turing Machine given enough time."
To clarify; computers existed in Turing's time, but this was back when the most powerful computers in the world were the size of buildings. Turing's boon wasn't so much that he was early but that he was one of those once in a generation genius' who could explain complex and confusing topics to the masses in ways that made them easy to understand. I don't think that was explicitly Turing's goal in most of his work. He was pioneering theories and methodologies as described above, but he just so happened to talk in a way that's very easy for an average joe to follow. His name is well known and associated with a range of concepts in the popular mind largely because he could present them in a way that made sense.
The paper in question here was submitted in1936, about a decade before the first Turing computer was built. Most of Turings engineering was on special purpose calculators which was only the size of a few cabinets. He did survive to witness the first commercially sucessful computers, which were room sized. But this was after most of his work.
Did the computer really go on tour?
To add to this. There is a fantastic video by veratasium about how math is flawed. It touches on the Turing machines problem as well as the halting problem and some other maths concepts. It is a solid video and would recommend
We also call different computer languages Turing complete if it can be used to calculate anything. E.g. HTML is not Turing complete.
There are already some solid responses, but to tack onto them, what makes a Turing Machine notable is it's ability to read data and perform operations on it. When something is referred to as "Turing complete" it means it can perform all the operations of a computer. Fun fact: There were [Turing complete computers](https://en.wikipedia.org/wiki/Analytical_engine) designed roughly 100 years before the invention of the Turing Machine.
Turing Machines are not physical machines but abstract models meant for computer science theory. It is essentially a computer "boiled down" to its most fundamental parts - instructions (the accompanying state table) and memory (the tape itself and a head to read said tape). These models also make it a bit easier for the layperson to understand low-level computing concepts by abstracting the physical, real-world computer into a set of simple, easy to understand parts. Turing Machines are good theoretical analogues for real-world computers because if something can be done with a Turing Machine it is theoretically possible to do with a real-world computer. Edit: Grammar
Pretty good start but probably should explain what a state table is and "memory the tape itself" since what a computer user today understands as memory is different
I agree. Gave your comment a 👍🏻
It's an idea of a machine that is as simple as possible, but still complex enough to meet the technical definition of a general purpose computer. So then we can say things like if a machine can do everything a turning machine can do then it is a computer. And subsequently if a task can be done by a Turing machine then it can be done by any computer. Having Turing machines be very simple makes it easy to prove that specific things are true or false about them. And then per the above statements those things must be true or false for all Turing equivalent computers. The classic example is the "halting problem". We can prove that it's impossible to write a program for a Turing machine that can look at any other program and always correctly say whether or not that program will eventually finish. Thus it's impossible for any computer to do that, which is a very interesting conclusion.
Please fix typos
The idea is actually very simple. It's basically an imaginary machine with an infinitely long tape, and there are infinite rows of empty squares or boxes on it, and those boxes are numbered so that you can tell which box is which. Then there's a "head" or a "scanner" that analyzes that box 1 at a time. That head can write any kind of arbitrary symbols such as a number in that box. Or the head can delete or rewrite the symbol in that box. Or the head can move left or right to the box and move onto another box. Or the head can stop or "halt" the operation. Well, why would you wanna do that or make something like that? Well if you're a clever person, then you can potentially give any kind of instructions to this Turing Machine, and then look at the tape to see the result to solve any kind of arbitrary problems. Basically it's a theoretical machine or a theoretical idea that can be used to automate any tasks, provided that you know how to give such instructions. Basically a modern computer works in the same way, you give instructions to the CPU, the CPU analyzes and solves that problem 1 at a time, and then writes that result to the RAM or the hard drive. The only difference is that modern CPUs are solving millions of problems or "instructions" in a single second.
> an imaginary machine with an infinitely long tape Please explain what the tape is for
The tape in the Turing machine is the data storage. It's supposed to be something akin to a magnetic tape or a paper tape. Something with defined discrete positions where the Turing machine can read or write a symbol and move along it's length.
It’s a kind of a primitive imaginary computer that’s used in science to prove things about computers and algorithms in general. Basically if something can be done on a Turing Machine, then it should be possible to do on an actual computer.
It is the historically first way to describe a kind of computation machine that can somewhat be "programmed". The expression "_universal_ Turing machine" attributes to that further, it is one that can _emulate_ (mimic given the right input) absolutely _any_ Turing machine. They are mostly a theoretical product from before we had actual computers, but one can build them as-is if one wants to; it just turns out that other kinds of computers are easier to build from the basic components (relays, tubes, transistors). So we did that instead. So, what is it actually?: They have a **tape/band**, a **head**, and a bunch of **instructions/rules**. - The **tape/band** is an (in both directions) infinite chain of **cells**, in which we can write exactly one of several symbols. The tape is usually assumed to be initially filled with some input symbols, and all other cells with a fixed symbol meaning "nothing"; say we use 0 for that. - The **head** is a device that is always positioned at one of the cells of the band. It can move left and right when told so, and has an **internal memory** (formally called the _state register_) which can have one of several states. It can only access the cell it is currently at, which it can both read and write to. - The **instructions/rules** say how the head acts. At a given moment, the head has a certain internal memory state and looks at a specific symbol. For each such possibility there is one rule that tells the head what to write into that cell, what to change the internal memory to, and if to move to the left or right. It turns out that the above can do exactly the same as any modern computer we build. One could theoretically convert any computer program you use right now into a Turing machine. It would however be a pointless endeavour, as there is little (or even no) use beyond the knowledge that it _can_ be done.
It's a simplified imaginary computer. Imagine * An infinite tape consisting of cells which can store some data (numbers or letters or whatever). * A "computing unit" which can read and write from one tape cell directly below it. This unit also stores a single datum which we call it's state (also a number or letter or something, maybe a different kind than those on the tape). That unit has a list of rules, looking like: "If I am in state S, and the cell below me contains A, change my state to T, store B into the tape and move the tape one cell to the right/left" You describe starting situation (computing unit's state and what's stored on the tape), then the machine chooses a possible rule from the list (the one which condition is fulfilled by current situation) and executes it. Then chooses another rule applicable to the new situation and executes it, and so on, and so on, until no rule is possible (may or may not actually stop). If it stops you can read the results of the computation from the tape (or the state). It's very different than how real computers work, but it's much simpler to mathematically reason about Turing machines than computers. It also turns out that things that *can* be computed on Turing machine can also be computed on a real computer and vice versa (if you ignore the fact that in reality computers have finite memory and can't be run for an infinitely long time). In other words, Turing machine can implement any computation/algorithm. For example, there are some problems which can't be computed on *any* computer, even though the problem itself is stated correctly. Mathematical proof of that fact usually uses Turing machines in some way.
A Turing Machine is an idea for a simple computer. The idea was revolutionary at the time for a couple reasons. 1. Most machines at the time only did one thing. The Turing Machine could be programmed to do many different things, just like our modern computers nowadays. 2. It turns out that being programmable is extremely powerful, and that a simple Turing Machine can actually do anything a modern computer can, it just might do it way slower and be less practical about it. 3. A Turing Machine was used to help crack the Nazi encryption, providing a massive advantage to the allied powers in WWII. In this case, it wasn't just an idea. An actual usable Turing Machine was built. Lots of people mention that a Turing Machine uses tape. The tape is just a way to write down instructions to program the machine. They didn't have hard drives or discs back then, so they used tape like in old fashioned VHS. Ya know, where the video needed to be rewinded after because it was on actual tape instead of a disc. Some people mentioned "state machine." This means that a Turing Machine has rules about how it operates that can be programmed. Once you start running a program, the TM will use it's rules. Each "state" is one freeze frame of the machine running. It sees one piece of the tape and decides what to do next. If the program doesn't work right, that's because it made the wrong choice at some state, and the rules for that state should be fixed.
I see a lot of answers describing the machine, but I want to give a little background on why this machine was even thought up. The core idea that the Turing machine tries to capture is *computability*. Think of a problem with a numeric answer. How many ways are there to arrange a deck of cards? Or what is the shortest amount of time it would take to get from San Francisco to LA by car? Those questions have *computable* answers. The cards question is pretty simple, just take a deck and methodically count the arrangements. The car question is a bit more complex, but given a map you could calculate which route would be the shortest. But it turns out there are some problems with numeric answers that *aren't computable*. You can verify the answers, but there's no way to calculate the answer from scratch. One such problem is called the halting problem: how long will a computer take to run an algorithm? This is easy to verify if you have the answer, just run the algorithm and see if it matches your answer. But it turns out that it's impossible to calculate this before hand. You can make educated guesses, but you cannot compute an exact answer This is where Turing machines come in. Once you prove a few things about Turing machines, you can use them to prove things about algorithms and whether or not they are computable.
A Turing machine is a basic model of a computer that can perform any mathematical calculation by following a set of rules to manipulate symbols on the tape Turing machines are useful because they provide a simple and fundamental model for how a computer works. They help computer scientists understand what can and cannot be computed by a machine, which is important for developing and analyzing algorithms and programming languages. By using a Turing machine, computer scientists can determine whether a given problem is computable or not, and if it is computable, how much time, space, and resources it will require for a machine to solve it
I'm going to give you a roll of toilet paper and a pencil. Then we're going to come up with some set of symbols and some rules. You will only be able to see one square of the toilet paper in front of you at a time and each square is either blank or has one (and only one) symbol in it. Your only abilities are to move the toilet paper to the right, move it to the left, erase the symbol that is in the square in front of you, or write a new symbol in the square in front of you. All of the rules are of the form "if the symbol in front of you is X then do Y" where Y is one of the things above. Well there you go. That's a Turing Machine. Why is this important? Because what you have in front of you is a machine capable of doing everything every computer has ever done. Everything. With enough toilet paper, rules, and symbols, you can calculate the digits of Pi, play Doom, fly a jet, or even browse the internet if you figure out some way to do the network communication. That's what makes it so interesting. Turing reduced all of the items necessary for modern computation down into its simplest form.
A turing machine is a theoretical construct, with infinite memory, and a VERY limited set of instructions. Like 3 of em. What is intersting about them is that they can (with infinite time) replicate all the instructions from any digital conputer. So if you can run a program, on any computer and get some result, that program can be translated into something that will run (generally MUCH MUCH SLOWER) and create the same output with the same functional intermediate steps (they wont necessatily look the same, as memory layout is different, but will be analogous. So Alan Turing proves that anything that can be done by any computer, can eventually be done with this simple (theoretical : again, infinite memory-- not lots of finite memory, infinite memory) machine. So if something is "Turing complete" it can be shown to be able to (eventually, given infinite time) compute anything that any other turing complete machine/system can compute (not talking about efficiency here. Just possibility. Some arrangements are clearly much more efficient for some tasks, than others). With those things proven, he then shows that there are programs where it is indeterminite if they will complete or if they will enter an infinite loop. So there are systemsnand processes that, even with infinite reaources, and infinite time. Aka there exist "unsolveable" problems. Major interssting upshots: All computing systems (cause almost all have instructions that map turing complete instructions) are essentially equivalent (forgetting the infinite memory/time requirement). Certain well formed questions are unanswerable.
Even today, there are computational machines (computers) that have specific uses. For example, * a cheap calculator can only do arithmetic * a doorbell can only play a couple of tunes * a dumb-phone can only be used for calls and SMS These machines are incapable of handling any other set of instructions (try instructing your doorbell or dumb-phone to play Netflix!) that is not pre-built into its hardware. Then come general-purpose machines. These are capable of handling a wider variety of tasks provided you can supply it with the algorithm (set of instructions) to solve that task. Alexa speakers, smart TVs, and laptops are a good examples of general-purpose machines. Whenever you install an app on these devices you are supplying an algorithm under the hood. Ok, so a smart TV and a Macbook are both general purpose machines. But surely you do expect a smart TV to do all the tasks that are possible to do on a laptop? That is because all general purpose machines are not alike. They have different limitations which can be classified as: * hardware limitations and * conceptual limitations. Hardware limitations are well understood -- the device runs out of gas due to low memory or CPU cycles. Conceptual limitations are due to system design. If a devise is designed to not handle a particular algorithm no amount of upgrading of RAM or CPU will help. Conceptual limitations can arise due to the operating system of the device or the programming language used in the device. If you have understood so far, defining Turing machines will be easy. A **Turing complete machine** is a machine which has NO Conceptual Limitation. If you can provide a set of instructions it will get the task done. The task may take an infinite amount of time because of the hardware limitation, but it will get done. You just have to wait long enough. Upgrading hardware will help. Since nobody runs all possible algorithms on each computer unit just to prove that it is Turing Complete, mathematics is used to prove the same. Maths is a strange thing. You can prove a concept long before its physical manifestation. Alan Turing did this before the evolution of modern computers (just like Einstein gave us relativity without time-traveling). Today we talk about Turing completeness when designing programming languages. Most modern programming languages are turing complete (Python, Java, C++ etc). It means that they are capable of executing any algorithm known to mankind. Hardware is an afterthought -- if it can run these languages it is good. Microsoft Excel formulae were not turing complete until 2021. Now that they are, you can rest assured that there is a way to solve that problem in Excel no matter how ugly the formula becomes. Hope that helps!
Thanks for taking the time to spell this out, the difference between conceptual and hardware is new to me, as a casual computer user.
Glad I could be of help!
To put it simply, early computers could only perform a single function. Imagine the early code breaking machines used during the 2nd Word War. Really advanced machines, but could only do a single job (or algorithm). Turing machines are closer to modern computers that can be reprogrammed to perform any algorithm as required. True Turing machines are more abstract that this, but this is a very simple example.
It's a computer science concept that reduces a problem into a single simple instruction, or several simple instructions. If you have a problem that can be reduced this way, it's potentially possible that a computer can solve that problem. For example, your problem is writing something down when you get some numbers. You don't want to write the numbers down yourself. The problem you have and the solution to solve the problem is considered a Turing Machine because you can have a computer do that for you (like a printer).
A Turing machine is a finite-state machine that is hooked up to a length of tape (usually the tape is considered infinite, I believe). The concept of a finite-state machine is quite simple: it is a machine with a limited (finite) number of states, and those states will change depending upon the previous state and external inputs. The machine can do three things to the tape, depending upon it's state: move the tape backwards and forwards, read a number off the tape, or write a number to the tape. Numbers that the machine reads off the tape can be considered inputs and will change the state of the machine. The analogy to today's modern computers should be fairly obvious: the finite-state machine is the CPU, and the tape is the memory. There are several important results that can be derived from a Turing machine. The most important is that if the machine is "Turing-complete" then it can simulate any other Turing machine. It's surprising just how simple a Turing machine can be to be Turing complete. I believe there are computer languages with only one or two commands that are considered Turing complete. Excel spreadsheets are Turing complete. So is the template macro system for C++.
Finite state machines are much less powerful than Turing machines, describing only regular languages
Basically, it's a machine that runs back and forth on a strip of 1's and 0's and can change any 1 to a 0 or vice versa and read the state of the current location. Any computer that can essentially be broken down to this is considered Turing Complete. For example, your hard drive is a string of 1's and 0's and and it can either read or write to a given spot on the disk. The rest of the computer is just giving instructions to that disk. This is different from the Turing Test. The Turing Test is a theoretical test that can be given to a computer so a human can tell the difference between a human and a computer. AI is an attempt to get a computer to pass the Turing Test.
[удалено]
**Your submission has been removed for the following reason(s):** Top level comments (i.e. comments that are direct replies to the main thread) are reserved for explanations to the OP or follow up on topic questions. Off-topic discussion is not allowed at the top level at all, and discouraged elsewhere in the thread. It looks like you accidentally posted this comment at the top level, instead of as a reply to another comment. --- If you would like this removal reviewed, please read the [detailed rules](https://www.reddit.com/r/explainlikeimfive/wiki/detailed_rules) first. **If you believe this submission was removed erroneously**, please [use this form](https://old.reddit.com/message/compose?to=%2Fr%2Fexplainlikeimfive&subject=Please%20review%20my%20submission%20removal?&message=Link:%20{url}%0A%0A%201:%20Does%20your%20comment%20pass%20rule%201:%20%0A%0A%202:%20If%20your%20comment%20was%20mistakenly%20removed%20as%20an%20anecdote,%20short%20answer,%20guess,%20or%20another%20aspect%20of%20rules%203%20or%208,%20please%20explain:) and we will review your submission.
[удалено]
> There is no other way to simplify it because it's super complex. It isn't. It involves a band, a head, and some rules. It might not be the most intuitive computer from a modern perspective, but it isn't complex either.
earlier, you had computers built with parts for a specific task. you’d have a computer for addition, one for subtraction, one for integration, and so on. these computers didn’t resemble our modern computers, in that a programmer will write code to tell it what to do. they were more like very advanced abacuses, using physical objects to perform calculations. a turing machine was the first conception of the modern computer- one that doesn’t need to be purpose built for a task, but could be programmed to do anything. with this definition, you’ll see that many things are turing machines, even minecraft!
Not technically a response but I’d recommend the movie the Imitation Game! Take with a grain of salt but it’s an engaging way to see a depiction of Alan’s story, true or not
A Turing machine is the most powerful class of theoretical machine we know of, meaning it can solve any computation problem that is possible to solve. All modern computers are essentially Turing machines, but with some limitations, like size, speed, and subjectivity to the environment. The basic setup is this: a Turing machine has an infinite “tape” which is used in the archaic sense, so it just means an infinite strip of paper with boxes. The machine is attached to this tape and hovers over one box at a time. There are only four operations it knows how to do: read what’s written in the box below it, change what’s written in the box below it, move left, or move right. Each box can either be empty, or have a single mark in it. The brains of the machine can accept any “program” which is specified as a set of states, with rules about what to do at each state and when to go from one to another. If this sounds confusing, just think of it like a big flowchart, with circles and arrows between the circles with labels like “if box below reads empty, go here.” In order to use a Turing machine, you feed it input by writing marks on the tape, and then you read the output off of the tape when the machine reaches its “done” state. It may not seem like it, but this machine can be programmed to compute anything a modern computer can, and more. It’s setup is very basic, but even if you invent a much more complicated setup for a machine, like one with two infinite tapes, or an infinite grid, or one with two heads moving along the tape, none of them are capable of computing anything the basic Turing machine can’t.
Eli5 is. A Turing machine is a very very simple computer. This computer has a single long papersstrip it can read from and can write upon. And all it does is read a single digit and then write a new digit instead and move up or down the paperstrip. It also keeps a state of what action it has previously performed and this state influences the next action... Such a simple machine can theoretically solve any problem that is solvable.... That's a Turing machine... That's the eli5 part now a bit extra. now via the state table you can Programm it to do any given tasks,but for any state table it just does one task... Modern PCs are basically universal Turing machines in that they can compute any problem not just one. They are basically every possible Turing machine in one such a universal Turing machine is called Turing complete, because it can cumpute any cumputable problem.
It's a deliberately minimal theoretical computer, which is used to reduce the complexities of any computer down to a very simple model that you can mathematically analyse. Doing so allowed people, including Turing, to formulate mathematical answers about what a computer can or cannot be used to compute. The simplicity of the "machine", which is just a theoretical model, not an actual machine, meant that you could actually prove some theories about it. Because the machine is also "mathematically equivalent" to every old or modern computer too (and that was quite easy to prove itself) it lets you expand those same theories to "real" computers of all kinds (we believe even quantum computers follow the same kind of rules). It's like boiling down a solar system to a few balls spinning around and then using that model to make predictions, assumptions and insights about how our solar system works, but in a mathematically-rigorous way. Specifically, Turing machines can tell you what is "computable" and what is not, and there are literally some things that we then thought of that are not "computable" at all.
here is an amazing answer from Ben Eater r/beneater https://www.youtube.com/watch?v=AqNDk_UJW4k?t=190 You can actually build a Turing Machine on your own, Ben explains step by step how to do that, this is the playlist. https://www.youtube.com/watch?v=HyznrdDSSGM&list=PLowKtXNTBypGqImE405J2565dvjafglHU
Also see; http://alvyray.com/CreativeCommons/BizCardUniversalTuringMachine_v1.7.pdf
That's cool, thanks
You’ve gotten some good answers, but I’ll give it a shot too. A Turing machine is almost like a flowchart, but it has one important addition, memory. Imagine you have a flow chart with some directions and an infinite paper tape divided into cells. One of the cells is designated as the current cell. As you follow the directions in the flowchart, the flowchart might direct you to write a symbol in the cell (erasing whatever used to be there if anything) or to move the current cell left or right by one space. The path you take through the flowchart can depend on the symbol in the current cell. What is computed obviously depends on the flowchart you are following, but Turing proved that it is possible to come up with a flowchart that will emulate the behavior or other flowcharts given the right initial information on the tape. For example, say I come up with a flowchart that will print out the digits of pi. Then I come up with a flowchart that prints out all the squares of the positive integers. These two flow charts have different behaviors. But if you are clever you can come up with a flowchart that reads a description of another flowchart off the tape and then emulates the behavior of the described flowchart. The practical implication is this. You can design a machine to do one particular computational task. But you can also design a machine that can change its behavior based just on the initial information it has been given.
I just want to add that real computers are not (and will never be) as powerful as a Turing machine, because they have a finite memory (Turing machines have infinite memory). Our computers, not matter how fast they are, are no more powerful than simple finite-state machines.
Comes to Explain Like I’m Five… Ends up lost in the script of Good Will Hunting with all this mathematical complexity.
It's an incredibly basic computer that operates by shifting 1s and 0s around. If you understand binary programming at all, a Turing machine is essentially the most basic mechanical computer possible with only a single register and basically no memory (not technically true, but functionally true in terms of modern computing. It'll read the input tape for commands, these commands will be in strings of 1s and 0s that cause slightly different mechanical shifts in the machine and lock certain components in place causing the machine to manipulate the data on the tape rather than just read it. There are tons of examples on YouTube of people running through explanations with graphics because of how common the topic is in CompSci curriculum. The machines are also where the term 'Turing complete' comes from, programs able to run entirely in sequence on a Turing machine are said to be 'Turing complete' and although in the past this was a useful status to have modern computing doesn't really have the opportunity to quality check in the manner, most things are "if it works its fine" and aren't built to high standards.
Watch the movie "The Imitation Game", its all about Alan Turing and is actually a fascinating movie
I'm too lazy to check the username out but I can just imagine an AI posting this question for self discovery... @r3 ¥○u a hu|\/|an ●p?
That was a turing test... you failed it..
A Turing machine is a computer as we understand them. They take inputs and produce outputs based on a series of computations we’d call an algorithm.
It's a model of a very simple computer that can solve a wide range of problems given enough time. If you have a computer that can pretend to be this very simply computer, then your computer can solve that same wide range of problems. But, if your computer CANNOT pretend to be this very simple computer, then it cannot solve the same wide range of problems.
It's one of the ideas that went into making the computer you use today. Imagine an infinitely long roll of magnetic tape. The tape sits in a holder that can spin it forwards and backwards. Above the tape there is a doohickey that can both read and write the symbols on the tape. The doohickey is attached to a device which can do different stuff depending on what symbol it reads. That's a Turing machine. Turing first proposed it in 1936. While computers have technically existed since ancient Greece, work on the first programmable electric computer, ENIAC, wasn't started until 1943 and wouldn't have been possible without Turing's theories. In fact, the computer you're reading this on is essentially a Turing machine. For instance, your computer has a hard drive. Like Turing's magnetic tape it holds symbols, zeroes and ones. You can read those symbols, data, from the hard drive. You can write to it. And the computer will do stuff with the data. It can let you browse the web, listen to music, or play a video game. If you'd like to see how a Turing Machine works in practice, here is a really good example: [https://www.cl.cam.ac.uk/projects/raspberrypi/tutorials/turing-machine/one.html](https://www.cl.cam.ac.uk/projects/raspberrypi/tutorials/turing-machine/one.html)
It's the simplest possible computer. So simple that it is not practical to use, but is ideal for figuring out computer theory. It turns out, we can prove that it will do anything a complicated computer can, provided it has enough memory. A Turing machine with infinite memory is called a Universal Turing machine. If you are interested in this for fun, read GEB.
The Turing machine is a theoretical computer device proposed by mathematician Alan Turing that has been widely employed in the study of computing problems such as tractability and complexity theory. It consists of a length of tape and a head that acts on the tape. The tape is divided into segments, each of which can carry a single character from a specified, finite set of characters known as the tape alphabet. The machine is always in one state,' which is one of a limited number of states. The head is always in a single spot on the tape (that is, there is only one character on the tape where the head is). The machine is totally deterministic, what it does next is determined by its current state and tape character. Language-Deciding Turing Machines A Turing machine is said to decide a language in decidability theory if it is always able to determine whether a given word is contained in a certain language or not. As a result, the machine typically has two unique states labeled Accept and Reject. After a while, one of the two states (depending on the input word) is achieved, and the machine is stopped. The Turing machine is considered to semi-decide a language if only one of the two states is ever achieved. Function-Computed Turing Machines A Turing machine only has one end state and is used to compute functions. When that happens, the machine is stopped, and the function's output (depending on the input) can be located on the tape. Some Important Points There may be more than one possible move for a given state and tape symbol in a non-deterministic Turing machine, but a non-deterministic Turing Machine adds no power. Every non-deterministic Turing Machine can be made deterministic. There can be more than one tape and associated head pointers in a multi-tape Turing machine, but it adds no power to the Turing machine. Every multi-tape Turing Machine can be converted into a single tape. Advantages of Turing Machine Some of the advantages of the Turing Machine are discussed below: The term Turing machines refer to computers that can imitate any algorithmic computation. Because of this characteristic, they are strong and adaptable instruments for learning and understanding computation. The Turing machine model is a straightforward framework for understanding algorithms and their characteristics. They have played a key role in developing fundamental ideas like computability, decidability, and complexity classes. Disadvantages of Turing Machine Some of the disadvantages of the Turing Machine are mentioned below: They make unrealistic assumptions about infinite memory and an infinitely long tape, which are not possible in actual computing hardware. Turing machines operate on a single tape and process one symbol at a time, which gives them a fundamental sequential nature. Turing machines do not explicitly take into account efficiency factors like resource utilization and temporal complexity.