notes-math-cs-coreOfUniversality

• arithmetic/logic gates (cite proposition 3, a basis for the nonzeroary Boolean operations, http://boole.stanford.edu/cs353/handouts/book3.pdf)
• substitution
• infinite looping
• self-reference
• partial, as opposed to total, function
• code as data

types of sub-turing computation

and what they're missing

• http://en.wikipedia.org/wiki/Primitive_recursive_function
  • missing http://en.wikipedia.org/wiki/Mu_operator (unbounded search) (see also defn part 6 at http://en.wikipedia.org/wiki/%CE%9C-recursive_function )
• (don't know if this exists or has a name) is there something that is like primitive recursion + unbounded search but admits only monotonic logic (e.g. AND and OR but not NOT)? If you can do arbitrary IF/THEN with constants then you can create a NOT. If you have the axiom of primitive recursion then you can define f(0) = 1 and f(1) = 0 (because you can arbitrarily define the base case and inductive step functions). Maybe if you restricted each of those with monotonicity you'd be good tho..
• bloop ( http://en.wikipedia.org/wiki/BlooP_and_FlooP )
  • missing unbounded looping (while loop or goto)
• http://en.wikipedia.org/wiki/Total_functional_programming
• https://dbohdan.com/wiki/jpeg-xl? (rule 110, so would be except limited to 1024x1024 blocks)

list of types of universal computers

• turing machine
  • similar: http://en.wikipedia.org/wiki/Counter_machine , http://en.wikipedia.org/wiki/Register_machine , http://en.wikipedia.org/wiki/Post-Turing_machine ,
• lambda calculus
• http://en.wikipedia.org/wiki/Combinatory_logic
• petri nets
• http://en.wikipedia.org/wiki/Markov_algorithm
• http://en.wikipedia.org/wiki/Rule_110 , http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life
• AEM see http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&ved=0CDQQFjAB&url=http%3A%2F%2Fwww.easychair.org%2Fpublications%2F%3Fpage%3D497436257&ei=O7uhUZaZJ8GZiQLRz4HABQ&usg=AFQjCNGW2A32k0UP8BIQv1hoHF30a9uhhw&sig2=vFj-ef9gFJ2ycURXG2gpYw&bvm=bv.47008514,d.cGE , http://www.aemea.org/msf/AEM.pdf , http://www.easychair.org/publications/?page=1303694832 (note that with regarding AEM's secrecy, it assumes that the adversary can see its firing patterns but cannot monitor fluctuations in its power consumption and does not know what program, with what inputs, it is running)
• http://en.wikipedia.org/wiki/Pointer_machine
• Rubino machine (Doug Rubino's unfinished but imo promising work)

see also http://en.wikipedia.org/wiki/Turing_machine_equivalents , http://en.wikipedia.org/wiki/Model_of_computation , http://en.wikipedia.org/wiki/Category:Models_of_computation , http://en.wikipedia.org/wiki/Abstract_machine , http://en.wikipedia.org/wiki/Turing_completeness , http://en.wikipedia.org/wiki/Church%27s_thesis, Gandy and Sieg's notions of informal computability ( http://en.wikipedia.org/wiki/Church%27s_thesis#Later_developments ), http://en.wikipedia.org/wiki/Hypercomputation , https://beza1e1.tuxen.de/articles/accidentally_turing_complete.html , https://www.gwern.net/Turing-complete