proj-plbook-plChSubturingModels

Table of Contents for Programming Languages: a survey

Chapter : sub-Turing models of computation

subrecursive languages including non-total functions

? any well known ones? todo

misc

An example of a widespread system that is not Turing Complete is Relational Algebra, the theoretical basis behind SQL as described in Codd's paper A relational model for large shared data banks. Relational Algebra has the property of Godel Completeness, which means that it can express any computation that can be defined in terms of first-order predicate calculus (i.e. ordinary logical expressions). However, it is not Turing-Complete as it cannot express an arbitrary algorithmic computation.

Note that most if not all all practical SQL dialects extend the pure relational model with procedural constructs to the extent that they are Turing Complete by the definition as normally applied to programming languages. However, an individual SQL query by and large is not." -- http://stackoverflow.com/a/449156/171761

toread: Subrecursive Programming Systems: Complexity & Succinctness (Progress in Theoretical Computer Science) by James S. Royer and John Case.

arguments for protocols to be context-free or regular: http://www.cs.dartmouth.edu/~sergey/langsec/occupy/ and http://www.cs.dartmouth.edu/~sergey/langsec/

Chomsky hierarchy

https://en.wikipedia.org/wiki/Template:Formal_languages_and_grammars

within each type, the most general subtypes are listed first, e.g. you have strict containment as you go down this list (todo doublecheck this for the stuff in type 1)

type 0

type 1

type 2

type 3

Complete problems for time and space complexity classes

For each class we list some complete problems of that class.

i think we have some strict containments known except for NP, which may be nonstrict: L < NL < CC < P <= NP

i don't know where NC fits it. NC^1 < L.

There's also some circuit classes ACC0 and TC0

DLOGTIME

NC

"decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors.", equivalently "those decision problems decidable by a uniform Boolean circuit (which can be calculated from the length of the input) with polylogarithmic depth and a polynomial number of gates." "the problems solvable on an alternating Turing machine restricted to at most two options at each step with O(log n) space and (\log n)^{O(1)} alternations.[6]" -- https://en.wikipedia.org/wiki/NC_%28complexity%29

NC = AC.

L

logspace

https://en.wikipedia.org/wiki/L_%28complexity%29

equivalent to https://en.wikipedia.org/wiki/SL_%28complexity%29

NL

Nondeterministic Logarithmic-space

see also https://en.wikipedia.org/wiki/NL-complete

CC

https://en.wikipedia.org/wiki/CC_%28complexity%29

P

(deterministic) polynomial time

https://en.wikipedia.org/wiki/P-complete

interesting subclasses within P are linear , nlogn ('linearithmic'), quasilinear, Sub-quadratic, and quadratic.

todo: http://mathoverflow.net/questions/80612/structure-of-class-p notes that the complexity classes of quadratic etc are not closed under composition and are sensitive to the definition of your machine, since different machine definitions sometimes tend to have polynomial effects on time. However imo it would still be interesting to find linear-complete, linearithmic-complete, quasilinear-complete, sub-quadratic-complete, and quadratic-complete problems (besides the obvious emulation of Turing machines running FOR loops) for logtime or logspace reductions on the most common machine model (I'm guessing a RAM Turing machine, but really we want whichever model gives us the results in https://en.wikipedia.org/wiki/Time_complexity#Complexity_classes such as linear to search every element in an arrya, n log n for quicksort, n^2 for bubble sort, n^3 for naive matrix multiplcation. Or, if logtime or logspace reductions are too restrictive, then try linear time reductions, or possibly just (n - 1) time reductions for polynomial times of degree n. here's a paper on the structure of quasilinear time: http://www.cse.buffalo.edu/~regan/papers/pdf/NRS95.pdf "On Quasilinear Time Complexity Theory" Ashish V. Naik, Kenneth W. Regan, D. Sivakumar.

NP

https://en.wikipedia.org/wiki/List_of_NP-complete_problems

other hierarchies

https://en.wikipedia.org/wiki/Grzegorczyk_hierarchy

(i find that one less interesting for our purposes b/c of the arbitrary-seeming restriction on primitive recursion)

also look into these and see if they are relevant:

https://en.wikipedia.org/wiki/Slow-growing_hierarchy https://en.wikipedia.org/wiki/Fast-growing_hierarchy

todo check out http://www.cstheory.com/stockmeyer@sbcglobal.net/survey.pdf for more todo read http://stackoverflow.com/questions/13899274/algorithmic-task-which-requires-quadratic-time todo read http://cs.stackexchange.com/questions/10886/the-complexity-class-fp

also there's the primitive recursive FUNCTIONALS

other toreads: