home | index | units | counting | geometry | algebra | trigonometry & functions | calculus
analysis | sets & logic | number theory | recreational | misc | nomenclature & history | physics

Final Answers
© 2000-2016   Gérard P. Michon, Ph.D.    

Computer Science


Also on this site:

Related Links (Outside this Site)

Wikipedia Portal  |  PhysLink.com  |  Physics Central
Speed of a Screaming Slingshot Monkey  by  Dmitriy Gekhman (2007).

Books

Computer Architecture:  A Quantitative Approach   Hennessy  &  Patterson. Computer Organization & Design   David A. Patterson,  John L. Hennessy.

Videos

Turing's Enigma Problem  (Part 1, Part 2, Dad)   by  Pr. David F. Brailsford.
 
border
border

Computability & Complexity Theory

The Vocabulary of Computability
FunctionGrammar, Language, SetMachine
ComputableRecursively enunerableTuring machine
Total computableRecursiveHalting Turing machine
 Primitive recursiveBounded loops
 Context-freePushdown automaton
 RegularFinite-state automaton

Computerphile video:  Chomsky Hierarchy   by  Pr. David F. Brailsford.


(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.

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


(2016-02-10)   Deterministic and nondeterministic machines
Some automata allow more than one transition for a given input.

 Come back later, we're
 still working on this one...


(2016-02-09)   Deterministic Push-down Automaton   (DPDA)
A  DPDA  can be used to parse  deterministic context-free languages.

 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-)


(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
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


 Alan M. Turing (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 SymbolOutput SymbolDirectionNext State
00 or 1Left or Right0 to n
10 or 1Left or Right0 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.

 Come back later, we're
 still working on this one...

Computerphile video:  Turing Machine Primer   by  David F. Brailsford.


 Alan M. Turing (2016-02-10)   Universal Turing Machine
A Turing machine executing a program stored on its data tape.

 Come back later, we're
 still working on this one...


 Alan M. Turing (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  Alonzo Church.

 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)


(2016-02-09)   Total Turing Machines:  Machines that always halt.
Recursive languages  are recognized by Turing machine that always halt.

 Come back later, we're
 still working on this one...

Machines that always halt   |   Primitive recursive functions


(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.
Ack012345678
0123456789
12345678910
235791113151719
3513296112525350910212045
413655332 65536 - 32 2 65536 - 3

 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)


(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  56
014613  ≥ 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).

 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...

Computerphile video:  Busy Beaver Turing Machines   by  David F. Brailsford.
 
Wikipedia   |   MathWorld   |   Tibor Radó (1895-1965)


(2016-02-09)   Turmites :  Two-dimensional Turing machines.
The best-known turmite on a square grid is  Langton's Ant.

 Come back later, we're
 still working on this one...

Langton's Ant  (MathWorld, Wikipedia  or  MathWorld)


(2016-05-19)   The Church-Turing Thesis
Every effective computation can be carried out by a Turing machine.

 Come back later, we're
 still working on this one...

Stanford   |   Wikipedia   |   MathWorld   |   Alonzo Church (1903-1995)

border
border
visits since February 10, 2016
 (c) Copyright 2000-2016, Gerard P. Michon, Ph.D.