Nondeterministic
computation and the Connes embedding conjecture
by
Kevin Hartnett (Quanta Magazine, 2020年03月04日).
Language equations.
|
Complexity Zoo.
Computerphile video: Chomsky Hierarchy by Pr. David F. Brailsford.
FSA are incapable of counting beyond a certain bound and thus cannot recognize a language involving unbounded balances.
The Dyck language, consisting just of balanced strings of parentheses is the simplest example of a non-regular language. It's named after Walther von Dyck (1856-1934) who formally defined groups in 1882.
[画像: Come back later, we're still working on this one... ]
Computerphile video: Same Story, Different Notation
by David Brailsford.
Finite-state machine
|
Automata-based programming
|
Automata theory
Automatic sequences
|
Cobham's Theorem
[画像: Come back later, we're still working on this one... ]
Pushdown automaton | Context-free grammar | Greibach normal form (GNF) | Context-free language | Noam Chomsky (1928-)
Few results of automata theory have nontrivial practical programming consequences. One of them is the following great theorem established in 1971 by Stephen Cook (1939-):
Any task which can be performed by a 2DPDA can be accomplished
in
linear time by a regular computer (with random-access memory).
Languages which can be recognized in linear time.
[画像: Come back later, we're still working on this one... ]
Cook's theorem (1971)
Partial
Memoization for Obtaining Linear Time Behavior of a 2DPDA
Torben Amtoft & Jesper L. Träff (1992).
Simulation of Two-Way Pushdown Automata Revisited
by Robert Glück
The simplest kind of Turing machines uses only a single read-write tape on which only two symbols (or "colors") can be written: 0 ("blank") and 1 ("mark"). More complicated Turing machines which allow more symbols and/or several tapes can be simulated by such a machine. So can "random-access" machines (which allow jumps of bounded magnitude on the tape). Such machines may be much faster but they're not more powerful.
Besides the halting state (the zero state) each state of an n-state binary Turing machine is fully described by a table of six entries:
Full description of a state in an n-state binary Turing-machineThere are N = 16 (n+1) 2 such descriptions. For enumeration purposes, we may assume that all such descriptions are distinct. Otherwise, we'd obtain an equivalent Turing machine with fewer states by retaining only one state of each description and using the label for that state whenever the labels of states with identical descriptions are quoted.
To fully describe an n-state Turing machine, we describe all its states as above and indicate which one is the starting state (it can't be the halting zero state, except in the trivial case of an empty Turing machine). We don't have to consider separately machines which differ only by the way their states are numbered. All told, the number of distinct n-state Turing machines is:
n C (N,n) where N = 16 (n+1) 2
The input parameters (if any) are on the read-write tape at a specific position when the machine is started.
[画像: Come back later, we're still working on this one... ]
Computerphile video: Turing Machine Primer by David F. Brailsford.
A decision problem is a question which can be phrased in the form of a yes/no question. It is said to be computable when there is a Turing machine which halts if and only if the answer is yes.
Because Turing machines form a countable set, there are only countably many computable decision problems. On the other hand, the set of all decision problems is uncountable.
Indeed, consider simply the decision problems which pertain to integers. They are in one-to-one correspondence with sets of integers (to each such decision problem is associated the set of integers for which the answer is yes ). By Cantor's theorem, the sets of integers are not countable. Therefore, this set of decision problems is uncountable and so is the more general set of all decision problems.
Thus, almost all decision problems are not computable.
The term halting problem itself was apparently coined by Martin Davis (b. 1928) who was, like Alan Turing (1912-1954) himself, a doctoral student of Alonzo Church (1903-1995).
[画像: Come back later, we're still working on this one... ]
A Turing machine which halts for every input tape is called a total Turing machine. The problem of deciding whether a given Turing machine is total is strictly more difficult than the halting problem (which only entails one specific input).
Computerphile video by Mark Jago | Wikipedia | Alan Turing (1912-1954)
There are several variants. The most popular one is the Ackermann-Péter function devised by Rózsa Péter (1905-1977):
(DC ACKERMANN (M N) (COND ((ZEROP M) (ADD1 N)) ((ZEROP N) (SELF (SUB1 M) 1)) (T (SELF (SUB1 M) (SELF M (SUB1 N)))) )) ; In the above, "SELF" stands for "ACKERMANN".Ackermann (m, n) is superexponential for m = 4 and beyond.
[画像: Come back later, we're still working on this one... ]
Computerphile video:
The Most Difficult Program to Compute?
by David F. Brailsford.
Ackermann function
|
Wilhelm Ackermann (1896-1962)
The standard problem pertains to binary (blank/mark) Turing machines with n internal states (halting state not counted).
The answer to the busy-beaver problem is known as Radó's sigma function (A028444). No computer program or systematic procedure can possibly be devised which would compute it for an arbitrary value of n.
Radó's Sigma FunctionThe Busy-beaver function was first described, in May 1962, by the Hungarian mathematician Tibor Radó (1895-1965) : "On Non-Computable Functions" (Bell System Technical Journal, 41, 3, pp. 877-884).
[画像: Come back later, we're still working on this one... ]
A challenge similar to the Busy Beaver Problem is to find the largest number which can be expressed with a prescribed number of keystrokes in a given computer language. For those languages which allow Turing-complete constructs within expressions, that can't be done. However, the puzzle is solvable in more restricted cases: Back in June 2002, I was able to give the largest possible Excel expression of any given length n...
Busy Beaver Turing Machines (17:55)
by David F. Brailsford (Computerphile, 2014年09月02日).
Wikipedia
|
MathWorld
|
Tibor Radó (1895-1965)
[画像: Come back later, we're still working on this one... ]
Stanford | Wikipedia | MathWorld | Alonzo Church (1903-1995)
[画像: Come back later, we're still working on this one... ]
Langton's Ant MathWorld,
Wikipedia and
Numberphile (4:28,
2:56)
|
Christopher Langton (1949-)
Fourmi de Langton (8:48 in French)
by David Louapre (#21, 2015年12月11日).
[画像: Come back later, we're still working on this one... ]
Cellular automaton
|
Conway's game of LIFE
|
John H. Conway (1937-2020)
Elementary cellular automaton
|
Wolfram code
|
Stephen Wolfram (1959-)
Rule 110 is
Turing-complete (2002)
|
Matthew Cook (1970-)
Le Jeu de la Vie
& "Règle 110" (18:40, in French) by David Louapre (#49, 2017年12月08日).
