Ciro Santilli @cirosantilli  40

There is a Turing machine that halts for every member of the language with the answer yes, but does not necessarily halt for non-members.

Non-examples: cs.stackexchange.com/questions/52503/non-recursively-enumerable-languages

Subset of recursively enumerable language as explained at: difference between recursive language and recursively enumerable language.

This is the classic result of formal language theory, but there is too much slack between context free and context sensitive, which is PSPACE (larger than NP!).

By Noam Chomsky.

A good summary table that opens up each category much more can be seen e.g. at the bottom of en.wikipedia.org/wiki/Automata_theory under the summary thingy at the bottom entitled "Automata theory: formal languages and formal grammars".

The opposite of from first principles.

There's exactly one field per prime power, so all we need to specify a field is give its order, notated e.g. as $GF(n)$.

Every element of a finite field satisfies $x^{order}=x$.

It is interesting to compare this result philosophically with the classification of finite groups: fields are more constrained as they have to have two operations, and this leads to a much simpler classification!