ENTRY COMPUTABILITY
Authors: Oliver Knill: nothing real yet Literature: not yet,
some lectures of E.Engeler on computation theory


+------------------------------------------------------------
| Church's theses
+------------------------------------------------------------

The generally accepted Church's theses tells 
that everything which is computable can be computed using a 
Turing machine. In that case, the problem to determine, whether 
a Turing machine will halt, is not computable. 


+------------------------------------------------------------
| cipher
+------------------------------------------------------------

A cipher is a secret mode of writing, often the result of
subsituting numbers of letters and then carrying out arithmetic
operations on the numbers.


+------------------------------------------------------------
| Coding theory
+------------------------------------------------------------

Coding theory is the theory of encryption of messages
employed for security during the transmission of data or
the recovery of information from corrupted data.


+------------------------------------------------------------
| Cooks hypothesis
+------------------------------------------------------------

Cooks hypothesis
P=NP. A proof or disproof is one of the millenium problems. 


+------------------------------------------------------------
| Graph isomorphism problem
+------------------------------------------------------------

Graph isomorphism problem It is not known whether graph isomorphism 
can be decided in deterministic polynomial time. It is an open 
problem in computational complexity theory. 


+------------------------------------------------------------
| Inductive structure
+------------------------------------------------------------

Inductive structure A set U with a subset A and 
operations g_1,...,g_n define an inductive structure (U,A,g_1,...,g_n)
If all elements of U can be generated by repeated applications of
the operations g_i on elements of A.  Examples:


 (N,A=0,1,g_1(a,b)=a+b, g_2(a,b)=a*b defines an inductive 
structure. 
 If U=N is the set of natural numbers, A=1,2,3
g_1(x,y)=3x-4,g_2(x,y,z)=7x+5y-z, then (U,A,g_1,g_2) define
an inductive structure. 



+------------------------------------------------------------
| syntactic structure
+------------------------------------------------------------

An inductive structure (U,A,g_1,...,g_n) is called a syntactic structure 
if it is uniquely readable that is if
g_1(u_1,...,u_k) = g_2(v_1,...,v_l), then g_1=g_2,k=l and
u_1=v_1,...,u_k=v_k. Example: if X is the set of finite words
in the alphabet  p,q,r,K,N  and A=p,q,r. Define
g_1(x,y) = Kxy and g_2(x,y)=Nx and U the set of words 
generated from A. The structure is the language of elementary logic 
in polnic notation. It is a syntactic structure. 
Syntactic structures are in general described by grammers.


+------------------------------------------------------------
| grammar
+------------------------------------------------------------

A grammar (N,T,G) is given by two sets of symbols N,T and a finite set G of
pairs (n_i,t_i) which define transitions n_i to t_i. For example:
N=S,T=K,N,p,q,r, G= S to p, S to q,S to r, S to KSS, S to NS .
Acoording to Chomsky, one classifies grammers with additional conditions
like context sensitivity or regularity. 


+------------------------------------------------------------
| context sensitive
+------------------------------------------------------------

A grammer (N,T,G) is called context sensitive if 
(n,t) in G then |t| geq |n|. 


+------------------------------------------------------------
| context sensitive
+------------------------------------------------------------


This file is part of the Sofia project sponsored by the 
Provost's fund for teaching and learning at Harvard university. 
There are 10 entries in this file.

COUNT: 10