(2016-02-09) Finite-State Automata (FSA)
The simplest kind of automata is used to recognize a regular language.
FSA are incapable of counting and cannot recognize a language involving unbounded balances.
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) 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
0 or 1
Left or Right
0 to n
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.
The input parameters (if any) are on the read-write tape
at a specific position when the machine is started.
(2016-02-10) Universal Turing Machine
A Turing machine executing a program stored on its data tape.
(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, who was, like Alan Ruring himself, a doctoral student of
A Turing machine which halts for every input tape is called a total
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) The Busy-beaver function isn't computable
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
No computer program or systematic procedure can possibly be devised which would compute it
for an arbitrary value of n.
Radó's Sigma Function
> 1.29 10 865
The Busy-beaver function
was first described, in May 1962, by the Hungarian mathematician
Tibor Radó (1895-1965) :
(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...