(2016-02-09) Finite-State Automata (FSA)
The simplest kind of automata is used to recognize a regular language.
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.
(2016-02-09) 2-way Deterministic Push-down Automaton (2DPDA)
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 by
Stephen Cook (1939-):
Any task which can be performed by a 2DPDA can be accomplished inlinear timeby a regular computer (with random-access memory).
(2016-02-09) Turing machines and utmost computing power.
Turing machines can accomplish as much as any other computer.
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-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 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:
(2016-02-10) Universal Turing Machine
A Turing machine executing a program stored on its data tape.
(2017-04-11) Decision problems (i.e., problems with yes/no answers).
Almost all decisions problems are not computable.
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.
(2016-02-03) The Halting Problem (Alan Turing, 1936)
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,
like Alan 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 total
is strictly more difficult than the halting problem
(which only entails one specific input).
(2016-02-09) Ackermann's Function
An example of a computable function that's not primitive recursive.
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.
(2016-02-09) The Busy-beaver function isn't computable
(Radó, 1962)
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 it
for an arbitrary value of n.
Radó's Sigma Function
0
1
2
3
4
5
6
0
1
4
6
13
≥ 4098
> 1.29 10 865
The 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).
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...
