"A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules."
Turing machines are abstract machines that can simulate any computer algorithm. They are used to define recursively enumerable languages and to study the limits of computation.
Formal Languages: The theory of formal languages and its relation to Turing Machines forms the basis of computation theory. It deals with the study of formal systems, such as grammars and automata, used for representing and manipulating language.
Computability Theory: This branch of computer science deals with the ability to solve problems with a computer. It explores the limits of computation, such as what problems can and cannot be solved using computational methods, including the Church-Turing thesis.
Turing Machine: Turing Machines are abstract computing devices, consisting of an input tape, a head that reads from and writes to the tape, a state transition function that determines the next state based on the current state and the symbol read by the head, and a set of final and non-final states. They are key to understanding formal language and computability theory.
Tape: The tape of a Turing Machine is the medium that holds the input, the work tape, and the output. It is infinite in length and is divided into cells, with each cell holding a symbol from a finite alphabet.
Head: The head of a Turing Machine is the device that reads and writes symbols on the tape. It moves left or right one cell at a time, depending on the current state and the symbol read.
State: The state of a Turing Machine is the current configuration of the machine, including the position of the head and the symbols on the tape. It changes as the machine executes.
Alphabet: The alphabet of a Turing Machine is the set of symbols that can be written on the tape. It is typically a finite set of characters.
Formal Definition: A formal definition of a Turing Machine is a set of states, the input alphabet, the work tape alphabet, the transition function, the start state, and the accepting states. It is a mathematical representation of the machine.
Universal Turing Machine: This is a type of Turing Machine that can emulate any other Turing Machine, and is therefore capable of universal computation. It is an important concept in computability theory.
Universal Language: A universal language is a language that can represent any other language. In the context of Turing Machines, the universal language is the language of programs that can simulate any Turing Machine.
Complexity Theory: This is the study of algorithms and the difficulty of computing problems. It deals with the classification of problems based on their difficulty and the development of efficient algorithms.
Deterministic and Non-Deterministic Turing Machines: A deterministic Turing Machine has a unique state transition for each possible symbol, while a non-deterministic Turing Machine can have multiple possible transitions for each symbol. Non-deterministic Turing Machines are useful for studying complexity classes such as NP-complete.
Church-Turing Thesis: The Church-Turing Thesis is a hypothesis that any function that can be computed by an algorithm can be computed by a Turing Machine. It is a central concept of computability theory.
Halting Problem: The halting problem is the problem of determining whether a given program will halt or run forever. It is an unsolvable problem, proven by Turing in his proof of the undecidability of the Halting Problem.
Post Correspondence Problem: This is a decision problem in computer science that deals with finding a solution to a certain type of puzzle. It is related to the theory of formal languages and automata theory.
Chomsky Hierarchy: The Chomsky hierarchy is a classification of formal languages into four types based on the complexity of their grammar. It is named after the linguist Noam Chomsky.
Pumping Lemma: The Pumping Lemma is a tool used in the theory of formal languages that shows that certain languages are not regular. It is used to prove theorems in automata theory.
Context-Free Languages: A context-free language is a formal language that can be generated by a context-free grammar. It is an important concept in the theory of formal languages.
Deterministic Turing Machine: It is a type of machine where the moves are uniquely determined by the current state and the symbol read from the tape.
Non-Deterministic Turing Machine: It is a type of machine where multiple moves can be taken from one state based on the current input.
Multi-Tape Turing Machine: It is a type of Turing Machine that has multiple tapes, and where the input is divided among the tapes.
Multi-Head Turing Machine: It is a type of Turing Machine that has multiple heads to read and write on the tape.
Multi-Dimensional Turing Machine: It is a type of Turing Machine that has a two or higher-dimensional tape.
Universal Turing Machine: It is a type of Turing Machine that can simulate any other Turing Machine.
Quantum Turing Machine: It is a type of Turing Machine that includes quantum mechanics principles and can potentially be more powerful than classical Turing Machines in solving some computational problems.
Probabilistic Turing Machine: It is a type of Turing Machine that randomly chooses which move to take from a current state.
Register Machine: It is a type of Turing Machine that uses a set of predefined instructions to move data between registers.
Tag System: It is a type of Turing Machine that uses tags to rewrite input strings.
Kolmogorov Complexity: It is a measure of the amount of information contained in a string that is obtained through Turing Machines.
"[...] it is capable of implementing any computer algorithm."
"The machine operates on an infinite memory tape divided into discrete cells, each of which can hold a single symbol drawn from a finite set of symbols called the alphabet of the machine."
"It has a 'head' that, at any point in the machine's operation, is positioned over one of these cells."
"[...] a 'state' selected from a finite set of states."
"At each step of its operation, the head reads the symbol in its cell."
"Then, based on the symbol and the machine's own present state, the machine writes a symbol into the same cell, and moves the head one step to the left or the right, or halts the computation."
"The choice of which replacement symbol to write, which direction to move the head, and whether to halt is based on a finite table that specifies what to do for each combination of the current state and the symbol that is read."
"The Turing machine was invented in 1936 by Alan Turing."
"Turing called it an 'a-machine' (automatic machine)."
"It was Turing's doctoral advisor, Alonzo Church, who later coined the term 'Turing machine' in a review."
"Does a machine exist that can determine whether any arbitrary machine on its tape is 'circular' (e.g., freezes, or fails to continue its computational task)? Does a machine exist that can determine whether any arbitrary machine on its tape ever prints a given symbol?"
"Thus by providing a mathematical description of a very simple device capable of arbitrary computations, he was able to prove properties of computation in general—and in particular, the uncomputability of the Entscheidungsproblem ('decision problem')."
"Turing machines proved the existence of fundamental limitations on the power of mechanical computation."
"their minimalist design makes them too slow for computation in practice: real-world computers are based on different designs that, unlike Turing machines, use random-access memory."
"Turing completeness is the ability for a computational model or a system of instructions to simulate a Turing machine."
"A programming language that is Turing complete is theoretically capable of expressing all tasks accomplishable by computers."
"nearly all programming languages are Turing complete if the limitations of finite memory are ignored."
"While they can express arbitrary computations, their minimalist design makes them too slow for computation in practice..."
"...real-world computers are based on different designs that, unlike Turing machines, use random-access memory."