(2016-02-09) The simplest kind of automata is used to recognize a regular language.
FSA are incapable of counting beyond a certain bound and thuscannot recognize a language involving unbounded balances.
(2016-02-10) Some automata allow more than one transition for a given input.
(2016-02-09) A DPDA can be used to parse deterministic context-free languages.
(2016-02-09) The 2DPDA and 2NPDA formal languages.
Few results of automata theory have nontrivial practical programming consequences. One of them is the following great theorem established in 1971 byStephen Cook (1939-):
Any task which can be performed by a 2DPDA can be accomplished inlinear timeby a regular computer (with random-access memory).
Languages which can be recognized in linear time.
(2016-02-09) Turing machines can accomplish as much as any other computer.
The simplest kind of Turing machines uses only a single read-write tapeon 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 tapescan 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-machine
Input Symbol
Output Symbol
Direction
Next State
0
0 or 1
Left or Right
0 to n
1
0 or 1
Left or Right
0 to n
There 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 onlyone state of each description and using the label for that state whenever the labelsof states with identical descriptions are quoted.
To fully describe an n-state Turing machine, we describe all its states as above and indicatewhich 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 waytheir states are numbered. All told, the number of distinct n-state Turing machines is:
The input parameters (if any) are on the read-write tapeat a specific position when the machine is started.
(2016-02-10) A Turing machine executing a program stored on its data tape.
(2017-04-11) Almost all decisions problems are not computable.
A decision problem is a question which can be phrased in the form of ayes/no question. It is said to be computable when there is a Turingmachine which halts if and only if the answer is yes.
Because Turing machines form acountable 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 suchdecision problem is associated the set of integers for which the answer is yes ). ByCantor's theorem, the sets of integers are not countable. Therefore, this set of decision problems is uncountable and so is the more general setof all decision problems.
Thus, almost all decision problems are not computable.
(2016-02-03) No program can tell whether a given program always terminates.
The term halting problem itself was apparently coined by Martin Davis (b. 1928) who was,likeAlan Turing (1912-1954) himself,a doctoral student of Alonzo Church (1903-1995).
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 totalis strictly more difficult than the halting problem (which only entails one specific input).
(2016-02-09) Recursive languages are recognized by Turing machine that always halt.
(2016-02-09) An example of a computable function that's not primitive recursive.
There are several variants. The most popular one is theAckermann-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.
Ack
0
1
2
3
4
5
6
7
8
0
1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
7
8
9
10
2
3
5
7
9
11
13
15
17
19
3
5
13
29
61
125
253
509
1021
2045
4
13
65533
2 65536 - 3
2 2 65536 - 3
(2016-02-09) How many marks could an n-state Turing machine make before halting?
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 itfor an arbitrary value of n.
Radó's Sigma Function
0
1
2
3
4
5
6
0
1
4
6
13
≥ 4098
> 1.29 865
The Busy-beaver function was first described, in May 1962, by the Hungarian mathematician Tibor Radó (1895-1965) : "OnNon-Computable Functions" (Bell System Technical Journal,41, 3, pp. 877-884).
A challenge similar to the Busy Beaver Problem is to find the largestnumber which can be expressed with a prescribed number of keystrokesin 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...
(2016-05-19) Every effective computation can be carried out by a Turing machine.
(2016-02-09) The best-known square-grid turmite is Langton's Ant (Langton, 1986).
(2019-12-08) Some of them are Turing complete, including Conway'sLIFE.
