# Type, operation and function, and their limits

First of all, sorry for my English.

I would like to know, when I want to define a new type (I'm currently developing a computer interpreted language), how can I determine which "functions" are fundamental operations for a particular type, and which "function" are external, in the sense that, I don't need this function to define the characterization of the type?.

Let me call "operations" to the "essential functions" of the type and "functions" to anything else that simply uses the type.

For example, we all agree (I suspect), that the sum, difference, product and division are good examples of "operations" that defines the type integer for example, or number in general, but an operation like factorial is more a function.

The question is, in a more general or theoretical point of view, where is the line between "function" and "operation" for the intended purpose? For example, for more abstract types like domain-specifics data structures, auxiliary classes or something more difficult than a "number", how or which test can I perform to say: that's a good as operation, or that's better being a function.

• The Church-Turing thesis shows us that no particular choice of operators is fundamental. There are many ways to achieve computation. The $\lambda$-calculus does this with just variables, abstraction and application. The $\pi$-calculus uses parallel composition, hiding and (asynchronous) pure message passing. Conways's game of life has an infinite number of cells continually exchanging one bit of information with it's 8 neighbours etc. – Martin Berger Aug 14 '13 at 13:19
• My question is more like thinking about types as an algebraic structure. Set of data + operations that work over elements in this set. For example, set of natural numbers and operations that performs an arithmetic, being this "arithmetic" the fundamental set of operations to define the nature of a "natural". I don't try to define "fundamentals of computation" or something like that, but "domains of computation"; more or less as 'axiom' does (axiom-developer.org). – Peregring-lk Aug 14 '13 at 14:30
• But you can typically set up data and operations in different ways. For example arithmetic (understood as Peano arithmetic) can be set up using ZF set-theory with the Axiom of Infinity negated (IIRC, please correct me if I'm wrong). That's a theory that doesn't have addition or multiplication as primitive operations. Algebraic operators and axioms can usually be defined in different ways. The choice is usually based on preference. – Martin Berger Aug 14 '13 at 18:24
• That's mean, there are no criteria to create a frontier between "function" and "operation" from a more algebraic point of view? For example, is there no criteria to say "the function/algorithm that performs the calculation of the minimum spanning tree of a graph, isn't a defining operation of the type graph because of ..."? Are there no criteria to complete the "..." part? Not even for practical purposes? – Peregring-lk Aug 14 '13 at 19:17
• You can impose constraints, like minimal number of algebraic operators to achieve this/that/the other degree of expressivity. But I doubt it's easy to show that any chosen non-trivial algebra is minimal in this sense, and I also doubt that there's always a unique minimal axiomatisation. Please think about complexity theory and in particular complete problems and reductions for a given complexity class: for example there are 1000s of NP-complete problems that are poly-time or log-space reducible to each other. – Martin Berger Aug 15 '13 at 10:24