{'fraction_non_alphanumeric': 0.04807737897681476, 'fraction_numerical': 0.007681001374994073, 'mean_word_length': 4.1861322842389965, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Comparing Computational Power

It is common practice to compare the computational power of different models of computation. For example, the recursive functions are strictly more powerful than the primitive recursive functions, because the latter are a proper subset of the former (which includes Ackermann's function). Side-by-side with this"containment"method of measuring power, it is standard to use an approach based on"simulation". For example, one says that the (untyped) lambda calculus is as powerful--computationally speaking--as the partial recursive functions, because the lambda calculus can simulate all partial recursive functions by encoding the natural numbers as Church numerals. The problem is that unbridled use of these two ways of comparing power allows one to show that some computational models are strictly stronger than themselves! We argue that a better definition is that model A is strictly stronger than B if A can simulate B via some encoding, whereas B cannot simulate A under any encoding. We then show that the recursive functions are strictly stronger in this sense than the primitive recursive. We also prove that the recursive functions, partial recursive functions, and Turing machines are"complete", in the sense that no injective encoding can make them equivalent to any"hypercomputational"model.


Introduction
Our overall goal is to formalize the comparison of computational models. We seek a robust definition of relative power that does not itself depend on the notion of computability. It should allow one to compare arbitrary models over arbitrary domains via a quasi-ordering that successfully captures the intuitive concept of computational strength. We want to be able to prove statements like "analogue machines are strictly more powerful than digital devices", even though the two models operate over domains of different cardinalities.
Since we are only interested here in the extensional quality of a computational model (the set of functions that it computes), not complexity-based comparison or step-by-step simulation, we use the term "model" for any set of partial functions, and ignore all the "mechanistic" aspects.

The Standard Comparison Method
There are basically two standard methods, Approaches C and S below, by which models have been compared over the years. These two approaches have been used in the literature in conjunction with each other; thus, they need to work in harmony. That is, if models A and A ′ are deemed equivalent according to approach C, while A ′ is shown to be stronger than B by approach S, we expect that it is legitimate to infer that A is also stronger than B.
Approach C (Containment). Normally, one would say that a model A is at least as powerful as B if all (partial) functions computed by B are also computed by A. If A allows more functions than B, then it is standard to claim that A is strictly stronger. For example, general recursion (Rec) is more powerful than primitive recursion (Prim) (e.g. [11, p. 92]), and inductive Turing machines are more powerful than Turing machines [1, p. 86].
Approach S (Simulation). The above definition does not work, however, when models use different data structures (representations). Instead, A is deemed at least as powerful as B if A can simulate every function computable by B. Specifically, the simulation is obtained by requiring an injective encoding ρ from the domain of B to that of A, such that for every function g computed by B we have g = ρ −1 • f • ρ for some function f computed by A, in which case A is said to be at least as powerful as B. See, for example, [8, p. 27], [3, p. 24], or [10, p. 30]: Computability relative to a coding is the basic concept in comparing the power of computation models.. . . The computational power of the model is represented by the extension of the set of all functions computable according to the model. Thus, we can compare the power of computation models using the concept 'incorporation relative to some suitable coding'.
Equivalence. To show that two models are of equivalent power by the simulation method, one needs to find two injections, each showing that every function computed by one can be simulated by the other. For example, Turing machines (TM), the untyped lambda calculus (Λ), and the partial recursive functions (PR) were all shown to be of equal computational power, in the seminal work Prim  [2], Kleene [7] and Turing [12].
More Powerful. To show that model A is strictly more powerful than model B, one normally shows that A is at least as powerful as some model A ′ that comprises more functions than B (A ′ B). (See, for example, [9].) Figure 1 illustrates this standard conception, according to which Turing machines are considered strictly more powerful than primitive recursion, since TM is equivalent to Rec-by simulation, and Rec is strictly more powerful than Prim-by containment.

The Problem
Unfortunately, it turns out that these two approaches, which form the standard method of comparing computational power, are actually incompatible. We provide examples in Section 3 of cases in which a model A is strictly more powerful than B by the first approach, whereas B is at least as powerful as A by the second. It follows that the combination of these two standard approaches allows for models to be strictly stronger than themselves! Specifically, in Example 4 below, we describe a model that is a proper subset of the recursive functions, but can, nevertheless, simulate all of them. This raises the question whether it could possibly also be the case that the primitive recursive functions are of equivalent power to Turing machines, via some "wild" simulation. Could it be that the recursive functions are of equivalent computational power to some proper superset, containing non-recursive functions?

The Suggested Solution
We begin (in Definition 3 below) with the basic comparison notion "as powerful as" ( ), using the simulation approach (Approach S), which naturally extends containment (Approach C) to models operating over different domains. (If a model A is as powerful as a B by Approach C, then it is also as powerful as B by Approach S.) Then the "strictly more powerful" partial ordering (≻) is derived from the quasi-ordering by saying that A ≻ B if A B but not B A, in other words, only when there is no injection via which B can simulate A.
To compare models operating over different domains requires some sort of mapping between the domains. A possible alternative might be to require a domain mapping that is not only injective but that also possesses additional properties, like being surjective. It turns out that bijective mappings not only cannot provide a sufficiently general comparison notion, but would be limited to permutations with bounded cycles (Theorem 1).
One is tempted to consider "well-defined" only those computational models that cannot be shown by simulation to be of equivalent power to any proper superset of functions. We call such a model "complete" (Definition 8). The question then is: Are the classic models, such as Turing machines, well-defined? In Section 5, we show that general recursive functions, partial recursive functions, and Turing machines are indeed all complete models in our sense (Theorems 6, 7, and 9). Accordingly, we obtain a criterion by which to verify that a model operating over a denumerable domain is hypercomputational (Corollary 5).

Definitions
We consider only deterministic computational models; hence, we deal with partial functions. To simplify the development, we will assume for now that the domain and range of functions are identical, except that the range is extended with ⊥, representing "undefined".
Two partial functions (f and g) over the same domain (D) are deemed (semantically or extensionally) equal (and denoted simply f = g) if they are defined for exactly the same elements of the domain (f (x) = ⊥ iff g(x) = ⊥ for all x ∈ D) and have the same value whenever they are both defined (f (

Definition 1 (Model of Computation) Let D be an arbitrary domain (any set of elements). A model of computation over D is any set of functions
Since models are sets: When A B, for models A and B over the same domain, we say that A is a submodel of B and, likewise, that B is a supermodel of A. Moreover, whenever we speak of A ⊆ B, we mean to also imply that the two models operate over the same domain.
To deal with models operating over different domains it is incumbent to map the domain of one model to that of the other. Let ρ : for any relation ρ and set of functions M . Additionally, we insist that ρ(y) = ⊥ iff y = ⊥.
This is the notion of "incorporated" used in [10, p. 29].
As a degenerate case, with the identity encoding ι (λn.n), we have A ι B iff A ⊇ B. Approach C of comparison (see the introduction) uses this simple relation.
Approach S is embodied in the following:

Proposition 1 The computational power relation between models is a quasiorder. Computational equivalence ∼ is an equivalence relation.
Transitivity of is because the composition of injections is an injection. Since the domain encoding ρ implies, by the simulation definition, a function mapping, we can extend ρ to functions and models, as follows: Definition 4 (Function Mappings) An encoding ρ : dom B → dom A induces the following mappings: from B to A and from A to B, respectively. These extend to sets of functions in the usual manner: Note that any function f , such that f ↾ rng ρ = ρ(g) ↾ rng ρ , simulates g via ρ, while ρ f is the only function simulated by f . The model ρ(M ) is minimal (with respect to the restriction of the domain to rng ρ) among those that simulate M via ρ, and ρ M is the maximal model simulated by M (see Lemma 1 below).
When π is recursive, one may speak of recursively isomorphism: function f is recursively isomorphic to g if there is a recursive permutation π, such that

Equivalent Submodels
Unfortunately, the above standard definition of "simulates" (Approach S, Definition 2) allows for the possibility that a model is equivalent to its supermodel.
Example 4 The set of "even" recursive functions (R 2 ) is of equivalent power to the set of all recursive functions. Define: We have that R 2 λn.2n Rec.
Furthermore, it leads to situations where A ≻ B ≻ A for models A, B. For example, the set of "odd" recursive functions (R 1 , defined analogously) is of equivalent power to the set of all recursive functions, by the same argument as above. We have that, R 1 Rec R 2 Rec R 1 , thus R 1 ≻ R 2 ≻ R 1 . Thus, the standard comparison method (Section 1.1) is ill-defined.
It turns out that the equivalence of a model and its supermodel is possible even when the encoding ρ is a bijection and the model is closed under functional composition. Hence, a model might be isomorphic to a supermodel of itself.

Definition 7 (Narrow Permutations)
Theorem 1 For every encoding ρ : D → D, there are models A and B, such that A B ρ A, iff ρ is a non-narrow permutation.
Proof. Suppose that π is a permutation with narrow cycles bounded by k. Assume A π B ⊇ A. There is, by assumption, a function f ∈ A, for every function g ∈ B, such that For the other direction, we must consider three cases: (1) non-surjective encodings; (2) surjective encodings that are not injective; (3) bijections with no bound on the length of their cycles. We can prove each case by constructing a computational model that is strongly equivalent to a supermodel of itself via the given encoding.
We provide here only a specific instance of case (3); the full proof is a generalization of the argument.
Let K be a set of "basic functions" over N, containing all the constant functions κ k (λn.k), plus the identity, ι. We present two models, A and B, that both contain the basic functions and are closed under function composition, such that the smaller one (B) simulates every function of the infinitely larger one (A).
Imagine the natural numbers arranged in a triangular array: If n is located on row m, then f i,j (n) is the number in row n + i and column j, while g i (n) is the first number in row n + i. Consider the following sets of functions: Note that F and G are disjoint, since for every i, j > 0 and n > j 2 , f i−1,j (n) < g i (n) < f i,j (n). Define: Thus, A has functions to jump anywhere in subsequent rows, while B A is missing infinitely many functions g i for getting to the first position of subsequent rows. Since, for i + k > 0, it follows that both F and G are closed under composition, as is their union F ∪ G, from which it follows that A and B are also closed.
There exists a (computable) permutation π of the naturals N, such that B π A: mapping numbers to their successor n + 1, but wrapping around before each square. That is, π has the following unbounded cycles: It remains to show that for all f ∈ A = K ∪F ∪G, we have π(f ) ∈ B = K ∪F . The following can all be verified: 2 Corollary 1 There are models isomorphic to supermodels of themselves.

Comparisons
One can categorize the maximal model that can be simulated, as follows: A and B, A ρ B

Lemma 1 For all models
Proof. We have B ⊆ ρ A iff for every g ∈ B there is f ∈ A, such that g = ρ −1 • f • ρ. This is the same as requiring that for every g ∈ B there is an By the same argument: Lemma 2 For all models A and B and bijections π, A π B iff A ⊇ π(B).

Corollary 2 For all models A and injections ρ, A ρ A .
Corollary 3 For all models A and bijections π, A ≃ π(A).

Lemma 3 For all models
Proof. Since π is a bijection, it follows that π(M ) is an injection (i.e. every function of M is simulated by exactly one function via π). Therefore, Proof. Suppose B π A for bijection π. Thus, A ⊆ π B . Let D = π C , for which we have C ≃ D. Since B C, it follows that A ⊆ π B π C = D. 2

Theorem 2
The primitive recursive functions, Prim, are strictly weaker than the recursive functions.
Proof. Clearly, Rec ι Prim. So, assume, on the contrary, that Prim ρ Rec. Let S ∈ Rec be the successor function. There is, by assumption, a function S ′ ∈ Prim such that S ′ • ρ = ρ • S. Since ρ(0) is some constant and ρ(S(n)) = S ′ (ρ(n)), we have that ρ ∈ Prim. Since ρ is a recursive injection, it follows that ρ −1 is partial recursive. Define the recursive function h(n) = ρ(min i {ρ(i) > ack(n, n)}), where ack is Ackermann's function. Since λn.ack(n, n) grows faster than any primitive recursive function and h(n) > ack(n, n), it follows that h / ∈ Prim. Since rng h ⊆ rng ρ, it follows that t = ρ −1 • h ∈ Rec. Thus, there is a function t ′ ∈ Prim, such that We have arrived at a contradiction: on the one hand, t ′ • ρ ∈ Prim, while, on the other hand, h / ∈ Prim. 2

Completeness
As shown in Section 3, a model can be of equivalent power to its supermodel. There are, however, models that are not susceptible to such an anomaly.

Definition 8 (Complete) A model is complete if it is not of equivalent power to any of its supermodels. That is, A is complete if
Theorem 3 1. Isomorphism of models implies their strong equivalence.

Strong equivalence of complete models implies their isomorphism.
Proof. The first statement is trivial. For the second, assume A π B τ A for bijections π, τ . If π A B, then, by Lemma 3, τ π A A, which contradicts the completeness of A. Thus B = π A , and therefore, A = π −1 B . 2 A is complete and A ρ B π A, for model B, injection ρ  and bijection π, then A and B are strongly equivalent models. Proof. Suppose A is complete, and A ρ B π A for injection ρ and bijection π. It follows that π B = A ′ ⊇ A. Thus, A ρ B π A ′ ⊇ A. Therefore, from the completeness of A, it follows that A ′ = A. Hence, A ′ −π B, and A and B are strongly equivalent models. 2

Theorem 4 If A and B are strongly equivalent models, then
Proof. Suppose that A is complete and A ≃ B C. By Lemma 4, C ≃ D A for some D. Were B C, then A ≃ B C ≃ D, contradicting the completeness of A. Hence, B is also complete. 2

Theorem 5 If model A is complete and A ≃ B
C, for models B, C, then C ≻ A.
Proof. If A ≃ B C, then C B A. And, by the previous theorem, if A is complete, then so is B; hence B C and also A C. Hence, C ≻ A. 2 We turn now to specific computational models. Analogously to the proof of Theorem 2, ρ ∈ Rec and ρ −1 ∈ PR. For every By the same token: The partial recursive functions PR are complete.

Corollary 4
The general recursive functions (Rec) and partial recursive functions (PR) are not strongly equivalent to any of their submodels or supermodels.
Proof. Non-equivalence to supermodels is just Theorems 6 and 7. Nonequivalence to submodels follows from Lemma 3. 2 As a corollary of Theorems 5 and 6, we obtain a criterion for hypercomputation: Proof. Since Rec is complete, it is sufficient, by Lemma 5, to show that Rec TM π Rec, for some bijection π. Since it is well-known that Rec TM via Gödelization (e.g. [6, pp. 208-109]), it remains to show that TM π Rec, for some bijection π. Define (as in [6, p. 131]) the bijection π : N → {0, 1} * , by

Discussion
There are various directions in which one can extend the work described above: Inductive Domains. The completeness of the (general and partial) recursive functions is due to several properties, among which is the inclusion of a successor function (Theorem 6). The results herein can be extended to show that computational models operating over other inductively-defined domains are also complete.
Intensional Properties of Completeness. Intuitively, a properly defined computational model should be complete. What is, however, "properly defined"? One can look for the intensional properties of a model that guarantee completeness.
That is, what internal definitions that constitute a model (e.g. a finite set of instructions, over a finite alphabet, . . . ) guarantee completeness.
Different Domain and Range. The simulation definition (Definition 2) naturally extends to models M : D k → D with multiple inputs, by using the same encoding ρ for each input component. See, for example, [10, p. 29].
A more general definition is required for models with distinct input and output domains. This can be problematic as the following example illustrates: Example 5 Let RE be the recursively enumerable sets of naturals. We define infinitely many non-r.e. partial predicates {h i }, which can be simulated by RE. Let h(n) = 0 program n halts uniformly 1 otherwise Without loss of generality, we are supposing that ρ(0) = h(0) = 0.

Firm comparison.
Comparison by an injective mapping between domains might be too permissive, as shown in Example 5 above. Accordingly, one may add other constraints on top of the mapping. For example, adding the requirement that the "stronger" model can distinguish the range of the mapping. That is, requiring a total function in the "stronger" model, whose range is exactly the range of the comparison mapping.
Multivalued Representations. It may be useful to allow several encodings of the same element, as long as there are no two elements sharing one representation, something injective encodings disallow. Consider, for example, representing rationals as strings, where "1/2", "2/4", "3/6", . . . , could encode the same number. See, for example, [13, p. 13]. To extend the notion of computational power (Definition 3) to handle multivalued representations, we would say that model A B if there is a partial surjective function η : dom A → dom B (η(y) = ⊥ iff y = ⊥), such that there is a function f ∈ A for every function g ∈ B, with η(f (x)) = g(η(x)) for every x ∈ dom η. This follows along the lines suggested in [13, p. 16]. The corresponding definitions and results need to be extended accordingly.
Different Cardinalities. It may sometimes be unreasonable to insist that the encoding be injective, since the domain may have elements that are distinct, but virtually indistinguishable by the programs. For example, a model may operate over the reals, but treat all numbers [n : n + 1) as representations of n ∈ N.
Effectivity. A different approach to comparing models over different domains is to require some manner of effectiveness of the encoding; see [4, p. 21] and [5, p. 290], for example. There are basically two approaches: 1. One can demand an informal effectiveness: "The coding is chosen so that it is itself given by an informal algorithm in the unrestricted sense" [8, p. 27].
2. One can require effectiveness of the encoding function via a specific model, usually Turing machines: "The Turing-machine characterization is especially convenient for this purpose. It requires only that the expressions of the wider classes be expressible as finite strings in a fixed finite alphabet of basic symbols" [8, p. 28].
Effectivity is a useful notion; however, it is unsuitable for our purposes. The first, informal approach is too vague, while the second can add computational power when dealing with subrecursive models and is inappropriate when dealing with non-recursive models.
Nondeterministic Models. The computational models we have investigated are deterministic (Definition 1). The corresponding definitions and results should be extended to nondeterministic models, as well.