notes-computer-programming-programmingLanguagesBook-programmingLanguagesChModelsOfComputation

Table of Contents for Programming Languages: a survey

Chapter : models of computation

Turing-equivalent systems

http://link.springer.com/chapter/10.1007%2F978-3-540-74913-4_120

" Turing Complete Catalytic Particle Computers

    Anthony M. L. Liekens,
    Chrisantha T. Fernando

Purchase on Springer.com

$29.95 / €24.95 / £19.95 *

The Bare Bones language is a programming language with a minimal set of operations that exhibits universal computation. We present a conceptual framework, Chemical Bare Bones, to construct Bare Bones programs by programming the state transitions of a multi-functional catalytic particle. Molecular counts represent program variables, and are altered by the action of the catalytic particle. Chemical Bare Bones programs have unique properties with respect to correctness and time complexity. The Chemical Bare Bones implementation is naturally suited to parallel computation. Chemical Bare Bones programs are constructed and stochastically modeled to undertake computations such as multiplication. "

von Neumann architectures, von Neumann bottleneck, massively parallel computing, computational architecture of the brain, 100 step rule

what else?

see also https://en.wikipedia.org/wiki/Computability#Formal_models_of_computation , https://en.wikipedia.org/wiki/Turing_machine_equivalents, https://en.wikipedia.org/wiki/Category:Models_of_computation, https://www.google.com/search?client=ubuntu&channel=fs&q=minimal+turing-complete+programming+language&ie=utf-8&oe=utf-8

http://programmers.stackexchange.com/questions/132385/what-makes-a-language-turing-complete

http://cs.stackexchange.com/questions/10197/a-program-that-cannot-be-written-in-simply-typed-lambda-calculus-but-only-in-l?rq=1

" up vote 10 down vote accepted

I always though that μ-recursive functions nailed it. Here is what defines the whole set of computable functions; it is the smallest set of functions containing resp. closed against:

    The constant 0 function
    The successor function
    Selecting parameters
    Function composition
    Primitive Recursion¹
    The μ-operator (look for the smallest x such that...)

Check above link for details; you see that it makes for a very compact programming language. It is also horrible to program in -- no free lunch. If you drop any of those, you will lose full power¹, so it is a minimal set of axioms.

You can translate those quite literally into basic syntactical elements for WHILE programs, namely

    The constant 0
    Incrementation _ + 1
    Variable access x
    Program/statement concatenation _; _
    Countdown loops for ( x to 0 ) do _ end
    While loops while ( x != 0 ) do _ end

Here it is obvious that you can drop 5.; what remains is a minimal set of operations your language has to support if it is to be Turing complete.

¹ You should be able to drop primitive recursion; I am not sure wether that causes technical issues, though. Or, maybe everything breaks as you can not even add two numbers anymore. shareimprove this answer

edited Apr 3 '12 at 5:48

answered Apr 2 '12 at 16:57 Raphael♦ 17.3k535106

2

Without primitive recursion, how do you define, say, addition? – Gilles♦ Apr 2 '12 at 17:14

μ-operator is defined in terms of primitive recursion (i.e. you should not have a operator under an operator). So you can't do nothing without primitive recursion! Thanks for the comparison with WHILE language, never thought about that! – Fabio F. Apr 15 '12 at 21:20 " -- http://cs.stackexchange.com/questions/991/are-there-minimum-criteria-for-a-programming-language-being-turing-complete

" The combinators S and K where, (S x y z)=(x z (y z)) and (K x y)=x are sufficient to express any (closed) lambda term, therefore any computable function. See this wikipedia page for details.

In fact, the lambda term X=λx.((x S) K) is a sufficient basis to express all lambda terms. See later in the same wikipedia page.

"

interesting link regarding the SKI combinatory calculus: http://brandon.si/code/do-applicative-functors-generalize-the-s-k-combinators/

this link has an example of the use of the Y combinator: http://raganwald.com/2008/05/narcissism-of-small-code-differences.html

Elements of models of computation

state (Turing tape, lambda calculus variables, combinatorial calculus explicit state argument)

isolated point(s) of execution (Turing head, lamdba calc and combinatorial calc current reduction, but not in cellular automata)

pointers (or references): (indirect addressing in most assembly languages; self-modifying code in Parallax Propeller; Turing self-modifying code? lambda calc variables? combinatorial calc eval?)

needs: pointers OR self-modifying code OR apply with variables OR eval ?

similary, needs: goto OR structured programming (see theorem) (call stack) OR eval OR recursion?

call stack? present in lambda calc certainly. in this merely a convenience elsewhere?

Chapter : models of concurrent computation

pi calc, actors, csp, etc