Based on a philosophical account of Incompletness Theorems, this paper will adress two new definitions of emergence. The first one is logical and relies directly on deductibility and Gödel-Rosser's Incompletness Theorems. The second one is algorithmic and relies on incalculability and Rice's Theorem. The latter has already been introduced in the literature under the name of « weak emergence » (Bedau, 1997), « dynamical emergence » (Collier, 2008), « cellular automaton » (Gu and al., 2008) or « emergent computation » (Forrest, 1990). The specificity of this work consists in providing a formal mathematical definition of the concept and discussing its applicability (pro and contra) to physical theories. More precisely, it is defended that algorithmic emergence, contrary to logical emergence, necessitates to view our physical world as discrete and infinite.

In a first step, the concept will be introduced by means of a intuitive example : the Collatz Conjecture. I will suggest that, if Collatz Conjecture were proven to be (logicaly) undecidable, one would have a very good example of a property that is both ”empirically” true and ”formally” irreducible to a definite set of fundamental axioms. This idea is supported by a theorem stating that for every given arithmetic, a sequence S for which a convergence property is ”true” but undecidable exists (Conway, 1972). The sequence S and the aforesaid ”convergence properties” are quite similar to the Syracuse Problem.

In a second step, it will be argued that no unique mathematical theory, complicated enough to express arithmetic, suffice to consistently explain every possible mathematical properties. This argument is trongly relatd to Gödel-Rosser's Theorem and will give us a formal definition of the so-called logical emergence.

In the third section will be addressed three mains objections about the applicability of the logical emergence to physical theories. These three objections are (I) Inapplicability (that the hypothesis of Gödel-Rosser's Theorem are not satisfied by physical theories) (II) Non-relevancy (that logical emergence applies only to metatheoretical properties, and not to physical phenomenons as such) and (III) Marginality (that logical emergence is not strong enough to express our wide intuition of what emergence is and to encompass all admitted emergent phenomenons in literature). In this debate, the importance will be emphasize on whether physical theories are discrete or continuous. A second distinction of mere importance is to know if emergence comes from our physical theories (epistemological point of view) or from the physical world (ontological point of view).

In the fourth section will be introduced a seemingly weaker, but also more applicable, version of emergence, which relies more on algorithmic calculability than on logical deductibility. This new definition will be illustrated by some examples in literature, as the Game of Life (Conway, 1970), the Ising model (Gu, 2008) and some considerations about Renormalization Group Theory (Fisher, 1998). The main question, in all these examples, is to know whether the physical world can be consistently described as an infinite and discrete lattice. This is a necessary condition for algorithmic emergence, but not for logical emergence, although the former is more workable than the latter.