O Teytaud

Why Simulation-Based Approachs with Combined Fitness are a Good Approach for Mining Spaces of Turing-equivalent Functions

We show negative results about the automatic generation of programs within bounded-time. Combining recursion theory and statistics, we contrast these negative results with positive computability results for iterative approachs like genetic programming, provided that the fitness combines e.g. fastness and size. We then show that simulation-based approachs (approachs evaluating only by simulation the quality of programs) like GP are not too far from the minimal time required for evaluating these combined fitnesses.

I. INTRODUCTION

@inProceeding{teytrice, author={O. Teytaud}, title={Why Simulation-Based Approachs with Combined Fitness are a Good Approach for Mining Spaces of Turing-equivalent functions}, booktitle={12 pages, proceedings of CEC}, year=2006 } Inspired by the genetic programming (GP) paradigm [START_REF] Koza | Genetic Programming: On the Programming of Computers by Means of Natural Selection[END_REF], [START_REF] Langdon | Foundations of Genetic Programming[END_REF], [START_REF] William | Genetic Programming and Data Structures: Genetic Programming + Data Structures = Automatic Programming!, volume 1 of Genetic Programming[END_REF], we investigate conditions under which the automatic generation of programs is possible. Precisely, we study programs aimed at generating programs for a given targettask, where the target-task might be provided by the user to the automatic generator as a black-box or as a Turingmachine number. In this spirit, we compare results derived from recursion theory applied to finite-time computations, and results on iterative algorithms derived from statistics and optimization in a spirit close to GP:

• we show universal lower bounds on the possible efficiency of (possibly randomized) programs aimed at optimizing in finite time i) the size, ii) the time complexity or iii) the space complexity. These results hold even within arbitrary large tolerance functions allowing strong sub-optimality. The uncomputability results are in particular stronger for the size of programs (i.e. they remain in the iterative case also, what does not happen for speed), what is related to the phenomenon of bloat (see below), which is an important issue in GP. • we then turn our attention to "blind" algorithms, that use only the target-task as a black box, and converge iteratively as in GP. Whenever previous negative results hold

Équipe TAO (INRIA Futurs), LRI, UMR 8623 (CNRS -Université Paris-Sud), Bat. 490, Université Paris Sud, 91405 Orsay CEDEX, France. Contact author: olivier.teytaud@lri.fr. O. Teytaud is partially supported by the Pascal Network of Excellence.

for bounded-time algorithms, we show positive results in an iterative convergence sense classical in optimization. Moreover, the positive results are proved thanks to population-based methods (keeping in memory a population of programs with their associated fitnesses) very related to GP methods. We then show lower bounds on the time complexity of iterative automatic program building, that are close to the simulation cost, thanks to a modified version of Kolmogorov's complexity ; this shows that the computational cost of simulation cannot be avoided ;

• we then show drawbacks that hold for fitnesses taking into account size alone or speed alone, and that do not hold for combined fitnesses using both ( [START_REF] Soule | Effects of code growth and parsimony pressure on populations in genetic programming[END_REF], [START_REF] Zhang | Balancing accuracy and parsimony in genetic programming[END_REF], [START_REF] Luke | Lexicographic parsimony pressure[END_REF], [START_REF] Nordin | Complexity compression and evolution[END_REF]).

We will need the following concepts in the paper:

• programming-programs are programs that output programs.

• finite-time algorithms take something as input, and after a finite-time (depending upon the entry), give an output. This is usually what we call an "algorithm". The opposite concept is iterative algorithms, which take something as input, and during an infinite time provide outputs, that are e.g. converging to the solution of an equation. Of course, the set of functions that are computable in finite time is included in (and different from) the set of functions that are the limit of iterative algorithms (see also [START_REF] Schmidthuber | Hierarchies of generalized kolmogorov complexities and nonenumerable universal measures computable in the limit[END_REF]). The (time or space) complexity of iterative algorithms is the (time or space) complexity of one computation of the infinite loop with one entry and one output. Therefore, there are two questions quantifying the overall complexity: the convergence rate of the outputs to a nice solution, and the computation time for each run through the loop.

• generalization is the process by which a function, calibrated in order to work on some entries, work also on other entries. The study of generalization is the main topic of statistical learning. A survey can be found in [START_REF] Lugosi | A probabilistic theory of pattern recognition[END_REF], [START_REF] Vapnik | The nature of statistical learning[END_REF], [START_REF] Bartlett | Neural network learning : Theoretical foundations[END_REF]. • genetic-programming ([9]) is the research of a program realizing a given target-task roughly as follows:

1) generate (at random) an initial population of algorithms ; 2) select the ones that, after simulation, look the most relevant for the target-task (this is dependent of a distance between the results of the simulation and the expected results, that is called the fitness) ; 3) create new programs by randomly combining and randomly mutating the ones that remain in the population ; 4) go back to step 2.

• bloat is the unexpected increase of the size of automatically generated programs. Bloat is an important issue in GP [START_REF] Langdon | The evolution of size in variable length representations[END_REF], [START_REF] Banzhaf | Some considerations on the reason for bloat[END_REF], [START_REF] Langdon | The evolution of size and shape[END_REF], [START_REF] Silva | Dynamic maximum tree depth : A simple technique for avoiding bloat in tree-based gp[END_REF], [START_REF] Ratle | Avoiding the bloat with probabilistic grammarguided genetic programming[END_REF], [START_REF] Soule | Exons and code growth in genetic programming[END_REF], [START_REF] Blickle | Genetic programming and redundancy[END_REF], [START_REF] Langdon | Fitness causes bloat: Mutation[END_REF]. • the absolute Kolmogorov complexity ( [START_REF] Solomonoff | A formal theory of inductive inference, part 1[END_REF], [START_REF] Solomonoff | A formal theory of inductive inference, part 2[END_REF], [START_REF] Kolmogorov | Logical basis for information theory and probability theory[END_REF]) of x is the size of the shortest program outputting x on the entry 0. We study in this paper a modified version, inspired by [START_REF] Buhrman | Resourcebounded kolmogorov complexity revisited[END_REF], [START_REF] Fortnow | Resource-bounded instance complexity[END_REF], [START_REF] Sipser | A complexity theoretic approach to randomness[END_REF], which is the size of the shortest program that outputs x on entry 0 and that works in time ≤ T . This modified version is computable, and we show lower bounds on its complexity.

II. DEFINITIONS & NOTATIONS

For the sake of clarity and without loss of generality, we consider Turing-machines [START_REF] Turing | On computable numbers, with an application to the entscheidungsproblem[END_REF], [START_REF] Rogers | Theory of recursive functions and effective computability[END_REF] (TM) with one (readonly) input tape, where the head moves right if and only if the bit under the reading head has been read, one internal tape (read and write, without any restriction on the allowed moves), one (write-only) output tape, which moves of one and only one step to the right at each written bit. The restrictions on the moves of the heads on the input and on the output tapes do not modify the expressive power of the TMs as they can simply copy the input tape on the internal tape, work on the internal tape and copy the result on the output tape. The space complexity is with respect to the internal tape (number of visited elements of the tape) plus the size of the program. All tapes' alphabets are binary. These Turing-machines can work on rational numbers, encoded as 2-uples of integers. Thanks to the existence of Universal Turing Machine, we identify TM and natural numbers in a computable way (one can simulate the behavior of the TM of a given number on a given entry in a computable manner). We use capital letters for programming-programs, i.e. programs that are aimed at working on programs. If x is a program and e an entry, then x(e) is the output of the application of x to the entry e. x(e) =⊥ is the notation for the fact that x does not halt on entry e. We also note ⊥ a program such that ∀e; ⊥ (e) =⊥. A program p is a total computable function if ∀e ∈ N; p(e) =⊥. A decider is a total computable function with values in {0, 1}. We note D the set of all deciders. We say that a function f recognizes a set F among deciders if and only if ∀e; (e ∈ F ∩ D → f (e) = 1 and e ∈ D \ F → f (e) = 0) (whatever may be the behavior, possibly f (e) =⊥, for e ∈ D). We say that two programs x and y are equivalent if and only if ∀e ∈ N; x(e) = y(e). We note this x ≡ y. We note ≡ y = {x; x ≡ y}. We note 1 = {p; ∀e, p(e) = 1}. The definition of the size |x| of a program x is any usual definition such that the number of states is upper-bounded by an increasing computable function of the size. We note (with a small abuse of notation as it depends on f and x and not only on f (x)) time(f (x)) (resp. space(f (x))) the computation time (resp. the space complexity) of program f on entry x. We note < x 1 , . . . , x n > a n-uple encoded as a unique number thanks to a given recursive encoding.

E is the expectation operator. P roba(.) is the probability operator ; by abuse, depending on the context, it is sometimes with respect to (x, y) and sometimes with respect to a sample (x 1 , x 2 , . . . , x m , y 1 , y 2 , . . . , y m ). Iid is a short notation for "independent identically distributed".

Overview of the paper Section III presents uncomputability results for finite-time algorithms. Section IV presents mainly computability results for the specialization on finite samples ; this section provides building blocks for section V which shows positive results for GP-like iterative algorithms. Section VI concludes.

III. FINITE TIME ALGORITHMS

We consider the existence of programs P (.) such that:

• the user provides x, which is a Turing-computable function ; • P (x) = y, where y ≡ x and y is not too far from being optimal (for size, space or time). Theorem 1 shows that for reasonable formalizations of this problem, such programs do not exist. This result is an extension of classical uncomputability examples (the classical case is C(a) = a).

Theorem 1 (Undecidability): Whatever may be the function C(.) in N N , there does not exist P such that for any total function x, P (x) is equivalent to x and P (x) has size

|P (x)| ≤ C(inf y≡x |y|).
Moreover, for any C(.), for any such non-computable P (.), there exists a Turing-machine using P (.) as oracle, that solves a problem in 0 ′ , the jump of the set of computable functions.

Proof: Assume, in order to get a contradiction, that such a P (.) exists.

Step 1: we study the behavior of P (.) on 1.

Then, define y as the shortest program such that y(e) = 1 for any entry e, and Y = {z; z ≡ y and |z| ≤ C(|y|)}. Y is finite.

Then, consider a program x that always halts. Necessarily, P (x) ∈ Y if and only if x ≡ y.

Step 2: show that thanks to P (if it exists), we can decide 1 (the class of programs that always reply 1) among deciders (indeed, more generally among computable total functions).

As Y is recursive (as it is finite), there exists a program

Q such that Q(e) = 1 if e ∈ Y and Q(e) = 0 otherwise.
Therefore, thanks to step 1, R = Q • P has the following property for any x that always halts: R(x) = 1 whenever x ≡ y and R(x) = 0 in other cases

Step 3: we now show that recognizing 1 among programs that always halt is as difficult as the domain-emptyness problem (that is known undecidable since Turing's fundamental paper [START_REF] Turing | On computable numbers, with an application to the entscheidungsproblem[END_REF]). Formally, we show that with an oracle recognizing 1 among deciders, there exists a Turing-machine only feeding the oracle with deciders that recognizes ≡ ⊥ .

Consider the following program S working on entry < x, < a, b >>:

• simulate a steps of x on entry b ;

• if it halts during this simulation then reply 0.

• if it does not halt, reply 1. This program S always halts. Then consider the following program working on entry x, using an oracle R(.). It recognizes 1 among deciders:

• if R(k → S(x, k)) = 1, then reply 1.

• otherwise, reply 0. This program replies 1 if and only if x never halts on any entry. Therefore, this program solves the emptyness of the domain of a Turing-machine (it recognizes ≡ ⊥ ). This is known as an uncomputable task, and more precisely it is in 0 ′ (the jump of the set of Turing-computable problems). Therefore, we have shown that no computable R(.) recognizing 1 among deciders can exist. As step 2 shows that the existence of a suitable computable P (.) implies the existence of such a computable R(.), such a computable P (.) does not exist.

We now show that using a random generator does not change the result.

Corollary 2 (No size optimization): Whatever may be the function C(.), there does not exist any program P , even possibly using a random oracle providing independent random values uniformly distributed in {0, 1} such that for any total function x, with probability at least 2/3, P (x) is equivalent to x and P (x) has size |P (x)| ≤ C(inf y≡x |y|).

Proof: We only simulate all the possible runs and modify the decision method in step 2 of the previous proof.

In the new second step, we simulate on a Turing machine, simultaneously 1 , all the possible behaviors of P until we reach a total probability > 1 2 of halting with P (x) ∈ Y or a probability > 1 2 of halting with P (x) ∈ Y . One of these two cases must necessarily occur by definition of P .

The extension from size of programs to time complexity of programs requires a more tricky formulation than a simple total order relation "is faster than" ; a program can be faster than another for some entries and slower for some others. A natural requirement is that a program that suitably works provides a (at least nearly) Pareto-optimal program [START_REF] Pareto | Manuale d'Economia Politica[END_REF], i.e. a program f such that there's no program that is as fast as f for all entries, and better than f for some specific entry, at least within a tolerance function C(.). The precise formulation that we propose is somewhat tricky but indeed very general:

Corollary 3 (Time complexity): Whatever may be the function C(.), there does not exist any program P , even possibly using a random oracle providing independent random values uniformly distributed in {0, 1}, such that for any total function x, with probability at least 2/3, P (x) ≡ x and there's no y ≡ x such that y Paretodominates P (x) (in time complexity) within C(.), i.e. 1 By "simultaneously" we mean that we simulate all the possible runs simultaneously, in a breadth-first manner.

∃y ∈≡ x and ∀z; time(P (x)(z)) ≥ C(time(y(z)))

and ∃z; time(P (x)(z)) > C(time(y(z)))
The result is also true when restricted to x such that a Paretooptimal function exist.

Proof: The proof is very similar to the previous proof. The only Pareto-optimal time complexity for 1 is a constant K (the time required to output 1 in the chosen encoding).

Therefore, for any entry x ∈ 1, P must generate a program in Y , where Y is the class of programs always outputing 1 and halting within time complexity ≤ C(K).

Y is not finite, but is recursive (lemma below). Within this modification, steps 2 and 3 of the proof of theorem 1 still hold.

We now prove the following lemma, useful in the proof above.

Lemma 4 (Computability for bounded-time): For any

(k, C) ∈ N, the set of computable functions f such that ∀x; time(f (x)) ≤ k and ∀x; f (x) = C is computable.
Proof: Consider the program that works as follows on a program p:

• write the tree of all the possible runs within the k first steps.

• if at least one of these runs does not halt withint the k steps, then reply "no".

• if at least one of these runs replies something else than C, then reply "no". • otherwise else, reply "yes".

After size (corollary 2) and time (corollary 3), we now consider space complexity (5):

Corollary 5 (Space complexity): Whatever may be the function C(.), there does not exist any program P , even possibly using a random oracle providing independent random values uniformly distributed in {0, 1}, such that for any total function x, with probability at least 2/3, P (x) ≡ x and there's no y ≡ x such that y dominates P (x) (in space complexity) within C(.), i.e., ∃y, y ≡ x and ∀z; space(P (x)(z)) ≥ C(space(y(z))) and ∃z; space(P (x)(z)) > C(space(y(z))) Proof: The proof is very similar to the two previous ones. We consider the same target-task (i.e. always writing 1 on the output tape). This can be performed within constant space complexity S. If such a P exists, then it must write, with probability at least 2/3, a program in Y , where Y is the class of programs writing 1 within space complexity C(S). This class is computable (lemma below), so steps 2 and 3 of the proof of theorem 1 hold within this modification.

Remark 6 (Other fitnesses):

We have proved the noncomputability result for speed, size and space. Other fitnesses (in particular, mixing these three fitnesses) lead to the same result. The key of the proofs above (th. 1, corollaries 2, 3, 5) is the recursive nature of sets of functions optimal for the given fitness, which is a very stable feature.

We now prove the following lemma, useful in the proof of the previous corollary 5.

Lemma 7 (Computability for bounded space): For any (k, C) ∈ N, the set S of computable functions f such that ∀x; space(f (x)) ≤ k and ∀x; f (x) = C is computable.

Proof:

• we recall that our definition of space complexity includes the size of the program. Therefore, TMs with a bounded space complexity have a bounded number of configurations2 ; they are finite automata in which some nodes have an output (recall that our TMs have restrictions on the possibility of moves of heads on the input and output tapes). Note A f such a finite automaton, associated to a T M f . • note Q = {q 1 , q 2 , . . . , q N } the finite set of states of A f , some of them being halting states and some of them outputing 1, some of them outputing 0, some of them not outputing anything, some of them reading the bit under the input head and some others not. Assume without loss of generality that q 1 is the initial state.

• define a new automaton A ′ f on the set of states Q × ∪ k l=0 ({0, 1} l ) where k is the length of C. • set the initial state of A ′ f at (q 1 , #)
where # is the empty string.

• define the transitions of A ′ f as follows: there is a transition from state (q i , S i ′ ) (where S i ′ is a binary string) to (q j , S j ′ ), with S j ′ = S i ′ .b (where . denotes the concatenation operator) when reading entry e on the input tape (possibly e is the empty string if A f does not read the input tape at state q j ), if and only if A f has a transition from q i to q j when reading e and A f outputs b (possibly the empty character if there's no output) in this case. note that A ′ f is a finite automaton without any writing hability.

• set the initial state at (q 1 , S 0 ) where S 0 is the empty string.

• then, f is in S if and only:

f can be consistently translated to A ′ f as explained above, and -A ′ f halts in Q × {C} on any entry. both these statements are decidable, therefore S is decidable.

IV. SPECIALIZATION ON A FINITE SAMPLE

We now turn our attention to the specialization on a finite sample. Results below will be used as building blocks for theorems of section V about iterative algorithms.

Theorem 8 (Specialization on a finite sample): a) There exists a program P such that ∀m ∈ N, ∀i ∈ [[1, m]], P (< x 1 , . . . , x m , y 1 , . . . , y m >)(x i ) = y i and P (< x 1 , . . . , y m > ) has optimal average (on the x i ) time complexity (resp. space complexity) , i.e.

1 n n i=1 time(P (< x 1 , . . . , y m > )(x i )) (resp. 1 n n i=1 space(P (< x 1 , . . . , y m >)(x i ))) min- imal.
b) There does not exist a program P such that ∀m ∈ N, ∀i ∈ [[1, m]], P (< x 1 , . . . , x m , y 1 , . . . , y m >)(x i ) = y i and P (< x 1 , . . . , y m >) has optimal size (i.e. |P (< x 1 , . . . , y m >)| minimal).

(we assume for consistency that x i = x j implies y i = y j ; we consider that the program P is right provided that it works in this safe case, whatever may be its behavior in other cases) c) For any (c 1 , c 2 , c 3 ) → c(c 1 , c 2 , c 3 ), non-decreasing computable function with limit +∞ as a function of c 1 or as a function of c 2 , there exists a program P such that ∀m ∈ N, ∀i ∈ [[1, m]], P (< x 1 , . . . , x m , y 1 , . . . , y m >)(x i ) = y i and P has optimal average (on i) cost, where the cost of program p on entry e is c(time(p(e)), space(p(e)), |p|).

Remark 9 (Fast programs do not generalize well): Note that a) in the case of time complexity is only of theoretical importance as Turing-machines optimal for time complexity on a finite set of cases are essentially very big Turing machines outputting the y i as soon as x i is recognized through a full-branching reading process. These machines work on the (x i , y i ) i≤m but not necessarily on unseen (x, y) (no generalization ability). The adaptation to c) is more concrete, as shown by theorems 10 and 11 below.

Proof of the theorem: a) is realized by the following program in the case of time complexity:

• compute the maximal time complexity T of the naive program comparing an input e to each of the x i , and replying y i if e = x i and replying 0 in other cases. • consider the programs of time complexity bounded by this time complexity. Simulate all of them within T steps ; there are infinitely many such functions, but we only have to take into accound the K states that can be reached within T steps, where K is the maximal number of states that can be visited by a program of time complexity ≤ T (for our Turing-machine formalism, K ≤ 4 T with binary tapes, as 2 binary values are read (one on the input tape and one on the internal tape). • simulate all of them until step T on all entries.

• select one of them which is optimal from the point of view of the average time complexity. The case of space complexity is similar. b) can be proved by the following reduction:

• assume that such a P exists ;

• consider the program e → |P (empty string, e)| ;

• this programs computes the absolute Kolmogorov complexity [START_REF] Solomonoff | A formal theory of inductive inference, part 1[END_REF], [START_REF] Solomonoff | A formal theory of inductive inference, part 2[END_REF], [START_REF] Kolmogorov | Logical basis for information theory and probability theory[END_REF], [START_REF] Chaitin | On the length of programs for computing finite binary sequences[END_REF], [START_REF] Chaitin | On the length of programs for computing finite binary sequences : statistical considerations[END_REF], what is not possible. c) is derived as a) ; the properties of c(., ., .) ensures that a finite set of functions can be considered (either the set of functions with bounded time complexity if c(., 0, 0) → ∞, which is finite is we restrict our attention to the finitely many possible time steps of simulation as in part a) of this proof, or functions with bounded space complexity if c(0, ., 0) → ∞).

Note that we have not ensured that the resulting program halts within the same time (resp. space) complexity on other entries than the x i , y i for i ∈ [ [1, m]]. We now have to prove that working on a sample might be efficient in generalization (ensuring that P (< x 1 , . . . , y m >) halts on any x and gives the right answer with probability 1, at least if m is sufficiently large). This is a problem of statistical learning (see e.g. [START_REF] Vapnik | The nature of statistical learning[END_REF], [START_REF] Lugosi | A probabilistic theory of pattern recognition[END_REF]). The usual general framework of statistical learning is as follows:

• Consider (x 1 , y 1 ), (x 2 , y 2 ), . . . , a sequence of iid (independent identically distributed) elements of N 2 , with common law P . (x i , y i ) is called an example. Restricting our attention to the case in which we work on consistent examples of a deterministic relation, we here consider that P (.) is such that for some total computable function f , P (f (x) = y) = 1. Many tools exist for studying such problems. The main question is a problem of generalization: finding a function that works on (x i , y i ) i≤m is easy (i.e. it is easy to design g such that ∀i < m, g(< x 1 , y 1 >, . . . , < x m , y m >)(x i ) = y i ), but does this function generalizes well to P ? A direct proof is possible in the current framework:

Theorem 10 (Learning from deterministic examples): Assume that y = f (x) with probability 1, where f is a computable function that always halts. Then, if (x 1 , y 1 ), . . . , (x m , y m ) is an iid sample with the same law as (x, y), then P roba(P (< x 1 , . . . , x m , y 1 , . . . , y m >)(x) = y) = 0 for m sufficiently large, almost surely in the sequence (x 1 , y 1 ), . . . , (x m , y m ), . . . , whenever f = P (< x 1 , . . . , y m >) is the first (for any enumeration of functions) computable function such that ∀i

∈ [[1, m]]; f (x i ) = y i .
In this theorem we do not here assume (and do not conclude) that P (.) is computable. This will be done in the next section after a slight modification of the paradigm. Note that the use of an order independent of the target-task has been investigated in GP (lexicographic order, see [START_REF] Luke | Lexicographic parsimony pressure[END_REF]).

Proof: Consider f the first function such that P roba(f (x) = y) = 0.

For any g < f , P roba(g(x) = y) > 0. Therefore, for any g < f , almost surely, there exists i g < ∞ such that g(x ig ) = y ig .

As the set {g; g < f } is finite, the previous sentence can be rewritten: almost surely, for any g < f , there exists i g < ∞ such that g(x ig ) = y ig .

For m > sup g<f i g , the property P roba(P (< x 1 , . . . , x m , y 1 , . . . , y m >)(x) = y) = 0 holds. The previous theorem holds for any P (.) verifying the required properties. Indeed, even if the order is computable, P (.) is not necessarily computable (e.g. it is not for an ordering by size). On the other hand, as stated in theorem 8, P (.) is computable if the order is the average time. Unfortunately, this is not in the scope of theorem 10, as the order depends on the examples whereas we need in theorem 10 an order that is not dependent on the data. Fortunately, the following theorem combines the advantages of both theorems 8 and 10: it provides a fitness such that P (.) is computable and generalization holds.

V. ITERATIVE ALGORITHMS

We have shown in section III that finite-time algorithms have deep limits. We have shown in section IV that iterative paradigms could converge to nice solutions (i.e. solutions that generalize well). We now have to proof that that iterative paradigms can be implemented on a Turing machine.

So, we now show in theorem 11 that the limit behavior of iterative paradigms can be reached by Turing-computable iterative algorithms. Theorem 12 is a refinement from the point of view of complexity.

The following theorem deals with learning deterministic computable relations from examples.

Theorem 11: Assume that y = f (x) where f is computable and P roba(f (x) =⊥) = 0 and Etime(f (x)) < ∞. Then, if (x 1 , y 1 ), . . . , (x m , y m ) is an iid sample with the same law as (x, y), then P roba(P (< x 1 , . . . , x m , y 1 , . . . , y m >)(x) = y) = 0 for m sufficiently large, almost surely. whenever f m = P (< x 1 , . . . , x m , y 1 , . . . , y m >) is a computable function f m such that ∀i; f m (x i ) = y i , minimal for the criterion c(ACT m (f m ), |f m |), where ACT m (g) is the average computation time of g on the x i and c(a, b) is any computable function, continuous and increasing as a function of a (which is rational) and increasing as a function of b, such that lim a→∞ c(a, 0) = lim b→∞ c(0, b) = ∞.

Moreover, c(Etime(f m (x)), |f m |) converges to the optimal limit:

c(Etime(f m (x)), |f m |) → inf f ;P roba(f (x) =y)=0 c(Etime(f m (x)), |f |)
and f m is computable from < x 1 , y 1 , . . . , x m , y m >. Proof: 1. Note f * an unknown computable function such that P roba(f * (x) = y) = 0, with Etimef * (x) minimal.

2. The average computation time of f * on the x i converges almost surely (by the strong law of large numbers). Its limit is dependent of the problem ; it is the expected computation time of f * on x.

3. By definition of f m and by step 2,

f m = P (< x 1 , . . . , x m , y 1 , . . . , y m >) is such that c(ACT m (f m ), |f m |) is upper bounded by c(ACT m (f * ), |f * |)
, which is itself almost surely bounded above as it converges almost surely (Kolmogorov's strong law of large numbers [START_REF] Khintchine | Sur la loi forte des grands nombres[END_REF]).

4. Therefore, f m , for m sufficiently large, lives in a finite space of computable functions {f ; c(0

, |f |) ≤ c(sup i ACT i (f * ), |f * |)}.
5. Consider g 1 , . . . , g k this finite family of computable functions.

6. Almost surely, for any i ∈ [ [1, k]] such that P roba(g i (x) = y) > 0, there exists m i such that g i (x mi ) = y mi . These events occur simultaneously as a finite intersection of almost sure events is almost sure ; so, almost surely, these m i all exist.

7. Thanks to step 6, almost surely, for m > sup i m i , P roba(f m (x) = y) = 0.

8. Combining 5 and 7, we see that

f m ∈ arg min G c(ACT m (g), |g|) where G = {g i ; i ∈ [[1, k]] and P roba(g i (x) = y) = 0}. 9. c(ACT m (g i ), |g i |) → c(Etime(g i (x)), |g i |) almost surely for any i ∈ [[1, k]] ∩ {i; Etime(g i (x)) < ∞ as [[1, k]] as c(., .
) is continuous with respect to the first variable (Kolmogorov's strong law of large numbers). As this set of indexes i is finite, this convergence is uniform in i.

10. c(ACT m (g i ), |g i |) → ∞ uniformly in i such that Etime(g i (x)) = ∞ as this set is finite.

10. Thanks to steps 8 and 9, c(Etime(f m (x)), |f m |) → inf g;P roba(g(x) =y)=0 c(Etime(g(x)), |g|).

We now turn our attention to a slightly modified definition of f m , which has the advantage of being more quickly computable. For the sake of clarity, the complexity below is with respect to a stronger form of machines, that can simulate n steps of machine x on entry e in time O(n), and computes ×, +, /,in O(1).

The following theorem deals with the complexity of learning Turing computable relations from examples.

Theorem 12: Assume that P roba(g(x) = y) = 0 for some computable g, and that Etime(g(x)) is finite.

Consider a Turing machine that works with an oracle tape providing a new example x m , y m at each request, and outputs f m on the output tape. The Turing machine works in-line, i.e. provides a new f m at each request on the oracle.

Then, within logarithmic factors or computational costs associated to the computation of a finite number of calls to c(., .), the following algorithm works with asymptotic time complexity O(L(m)) where L(.) is a non-decreasing computable function such that time(L(m)) = O(L(m)) (e.g. log 2 (.).

Define ∆ 0 = 1. Define t(f, 0) = 0 and for m ≥ 1 t(f, m) = 1 m ((m -1) × t(f, m -1) + min(time(f (x m )), L(m))).
Define P op 0 the empty population. Define f 0 a function that just outputs 1 and halts. Define ∀x; f it 0 (x) = 0. At each new example x m , y m (m ≥ 1):

• set P op m = {f ; c(0, |f |) ≤ min(∆ m , f it m-1 (f m-1 ))} ∪ P op m-1 . • for f ∈ P op m , define f it m (f ) = c(t(f, m), |f |). • for functions f ∈ P op m which finish in time ≤ L(m)
and reply some f An interesting point is that the proof involves an algorithm with a population of functions with their fitnesses in memory, what is very close to genetic programming. Proof: The steps of the proof are as follows:

(x m ) = y m , then set f it m (f ) = ∞. • define f m ∈ arg min P opm f it m • if f it m (f m ) > ∆ m-1 , then set ∆ m = ∆ m-1 + 1 ; otherwise, ∆ m = ∆ m-1 . Then L(f m ) → inf f ≡g L(f ) with L(f ) = c(Etime(f (x)), |f |),
• define f * = arg min {f ;f ≡g} L(f ). • define F = ∪ m∈N P op m .
• Assume, in order to get a contradiction, H1: F does not contain any f such that i) P roba(f (x) = y) = 1 and ii) f has finite expectation time.

• Then F is finite, otherwise else ∆ m → ∞ and inf F f it m → ∞ and therefore f * is in F . • Then, all f ∈ F have f it m (f ) → ∞. Proof: for each f ∈ F ,
-either there exists a, b such that P (x = a, y = b) > 0 and f (a) = b, and a, b will be drawn infinitely often, and in particular at some value of m for which L(m) ≥ time(f (a)) ; in this case, f it m (f ) reaches infinity. -or f does not have a finite expectation time, and f it m (f ) → ∞ by the lemma below (case 2).

• therefore, all fitnesses in F run to infinity. This leads to ∆ m → ∞. This implies that f * ∈ F ; this is a contradiction with H1. Therefore, H1 does not hold ; for m sufficiently large (say m ≥ m 0 ), some f ∈ P op m verifies P roba(f (x) = y) = 1 and f has finite expectation time. • then, for m ≥ m 0 , f it m (f ) ≤ f it m (f * ) ≤ K for some K > 0 as f it m (f * ) converges (cf lemma below, case 1). • therefore, ∆ m is also bounded above. Hence, F is finite.

• applying again the lemma below, we see that f it m (f ) converges to L(f ) uniformly in f ∈ F with finite expectation time and P roba(f (x) = y) = 1, and converges to infinity uniformly for other f ∈ F . This uniform convergence implies that L(f m ) → L(f * ). Step 2: lower bound. m m -e m = 1 m m i=1 max(0, x i -L(i)). For any m > m 0 ≥ 1, the right-hand-term is upper bounded by

1 m m0 i=1 max(0, x i -L(i)) →0 + m -m 0 m →1 1 m m i=m0+1 max(0, x i -L(m 0 )) →K(m0)
where the right-hand-term convergence is Kolmogorov's strong law of large numbers [START_REF] Poisson | Recherche sur la probabilité des jugements, principalement en matière criminelle[END_REF], [START_REF] Khintchine | Sur la loi forte des grands nombres[END_REF], with K(m 0 ) is the expectation E max(0, x-L(m 0 )). We now show that K(m 0 ) goes to 0 as m → ∞:

K(m 0 ) = E max(0, x -L(m 0 )) = n∈N max(0, n -L(m 0 ))P roba(x = n)
which goes to 0 by the monotone convergence theorem of Lebesgue [START_REF] Lebesgue | Intégrale, Longueur[END_REF].

Step 3: summary. So, for any m 0 , we can sum up previous steps by the fact that almost surely

e m ≤ m m →Ex and e m ≥ m m →Ex -(1 + o(1)) × 1 m m i=1 max(0, x i -L(i))
→m→∞K(m0)→m 0 →∞ 0 the second inequality holding for m sufficiently large.

Step 4: concluding. Therefore, for any ǫ,

• upper bound: for m sufficiently large, e m ≤ Ex+ǫ (first inequality in step 3), • lower bound:

-for m sufficiently large, m m ≥ Ex -ǫ/3, -with m 0 such that K(m 0 ) < ǫ/3 and for m ≥ m 0 sufficiently large, (1+o(1))× 1 m m i=1 max(0, x i -L(i)) ≥ K(m 0 ) + ǫ/3 and therefore for m sufficiently large e m ≥ Ex-ǫ/3. We have shown that finite time algorithms could not work properly (theorem 1, corollaries 2,3,5, remark 6). We have shown that iterative methods designing programs that are as fast as possible do not generalize well (remark 9), and that iterative methods designing programs that are as small as possible are not Turing-computable (theorem 8). We have also shown that iterative methods combining size and speed are Turing-computable and generalize well (theorem [START_REF] Lugosi | A probabilistic theory of pattern recognition[END_REF][START_REF] Langdon | The evolution of size in variable length representations[END_REF]. The complexity of Turing-computable programs defined therein is mainly the cost of simulation. We now show that it is not possible to avoid the complexity of simulation.

We first define a modified version of the complexity of Kolmogorov. We recall that Kolmogorov's complexity was first defined by Solomonov [START_REF] Solomonoff | A formal theory of inductive inference, part 1[END_REF] in the field of artificial intelligence also. Many other works about Kolmogorov's complexity exist, in particular adding constraints on resources ( [START_REF] Buhrman | Resourcebounded kolmogorov complexity revisited[END_REF], [START_REF] Fortnow | Resource-bounded instance complexity[END_REF], [START_REF] Sipser | A complexity theoretic approach to randomness[END_REF]); as far as we know, the following result is different and new (more closely related to the subject of this paper).

Definition 14 (Kolmogorov's complexity in bounded time): An integer x is T ,S-complex if there is no Turing machine M such that M (0) = x ∧ |M | ≤ S ∧ time(M (0)) ≤ T . M is the T -time-reduction of x if and only if M (0) = x, time(M (0)) ≤ T , |M | is minimal among possible functions (and, for the sake of unicity, M is the first in lexicographic ordering among M 's with the same size). Consider an algorithm A deciding wether an integer x is T , S-complex or not. Define C(T, S) the worst-case complexity of this algorithm (C(T, S) = sup x time(A(< x, T, S >))). It is finite for some A(.), even if there's no limit on the size of x as if x is too large, it is T n ,S n -complex whatever may be its value. We restrict our attention to such C(., .), corresponding to algorithms with computation time only depending upon T and S.

These notions are computable, but we will show that their complexity is large. The complexity of the optimization of the fitness in theorem 4 is larger than the complexity C(., .) of deciding if x is T ,S-complex ; therefore, we will lower bound C(., .).

Theorem 15 (The complexity of complexness): Consider now T n and S n , computable increasing sequences of integers computable in time Q(n) where Q is polynomial, and y n the smallest integer that is T n ,S n -complex. Then, for some

S n = O(log(n)), C(T n , S n ) > (T n -Q(n))/P (n).
where P (n) is a polynomial, and in particular if T n is Ω(2 n ),

C(T n , S n ) > T n P ′ (n)
where P ′ (.) is a polynomial, i.e. essentially we can not get rid of the computation time T n .

The proof follows the lines of the proof of the noncomputability of Kolmogorov's complexity by the so-called "Berry's paradox", but with complexity arguments instead of computability arguments.

Proof:

Step 1: y n is T n ,S n -complex, by definition.

Step 2: But it is not Q(n)+y n ×C(T n , S n ), C+D log 2 (n)complex, where C and D are constants, as it can be computed by

• computing T n and S n (in time Q(n)) • iteratively testing if k is T n , S n -complex, where k = 1, 2, 3, . . . , y n (in time y n × C(T n , S n ).
Step 3: y n ≤ 2 Sn , as:

• there are at most 2 Sn programs of size ≤ S n ,

• therefore there are at most 2 Sn numbers that are not T n , S n -complex.

• therefore, at least one number in [[0, 2 Sn ]] is T n , S ncomplex.

Step 4: if S n = C + D log 2 (n), then y n is upper bounded by a polynomial P (n) (thanks to step 3).

Step 5: combining steps 1 and 2, y n C(T n , S n ) > T n -Q(n).

Step 6: using step 4 and 5, C(T n , S n ) > (T n -Q(n))/P (n), hence the expected result.

VI. CONCLUSION

Let's now sum up and compare our results.

• in corollaries 2, 3, 5 we have shown that finite-time programming-programs can not perform the required task, i.e. finding the most efficient function in a space of Turing-equivalent functions. Ie, finite-time programs can not do the job (finding an optimal function in a space of Turing-equivalent functions) in the general case (corollaries 1, 2, 3). Iterative programs can do it, but only with mixed fitnesses (theorem 2b, remark 2). Then, the time-complexity of such fitness-optimization can not get rid of the simulation time (theorem 6).

In section III, we show negative results for the task consisting in writing in finite time a program realizing a given target-task in a neary optimal manner. These results are true for deterministic programming-programs, randomized programs, working on an oracle describing the target-task under the form of a program or a black-box oracle as well. These results concern time complexity, space complexity, and program size, and are true even within arbitrary tolerance functions C(.).

In section V, we show positive result for the specialization on a finite sample. Learning on a finite sample with a pragmatic compromise between length and speed leads to a function which is equivalent to the real one, and which is optimal for this compromise.

We can conclude as follows when the "target" function is a computable one:

• for various criterions (size, time complexity, space complexity), it is not possible to have a finite-time procedure that takes as input a program, and automatically generates an optimal program. • the size is the most undecidable criterion, as even on a finite sample it remains undecidable. This is related to the so-called "bloat" phenomenon [START_REF] Langdon | The evolution of size in variable length representations[END_REF], [START_REF] Banzhaf | Some considerations on the reason for bloat[END_REF], [START_REF] Langdon | The evolution of size and shape[END_REF], [START_REF] Silva | Dynamic maximum tree depth : A simple technique for avoiding bloat in tree-based gp[END_REF], [START_REF] Ratle | Avoiding the bloat with probabilistic grammarguided genetic programming[END_REF], [START_REF] Soule | Exons and code growth in genetic programming[END_REF], [START_REF] Blickle | Genetic programming and redundancy[END_REF], [START_REF] Langdon | Fitness causes bloat: Mutation[END_REF]. • it is also not possible to do it from examples, and to assert after finitely many examples that the work is done and that the optimal function is found. • on the other hand, it is possible to converge to a function that will match all future examples. Moreover, the resulting function will have its value, for a compromise between speed and size, optimal.

A remarkable fact is that the positive results occur for algorithms ignoring the internal structure of the program. This is a deep argument in favor of genetic programming. Note that our results also show that optimizing speed alone is not suitable on a finite sample of x i , y i , as very big naive programs are very fast, and that optimizing size alone is not Turing-computable ; compromises between size and time are more suitable. This is in favor of coupled fitnesses ( [START_REF] Soule | Effects of code growth and parsimony pressure on populations in genetic programming[END_REF], [START_REF] Zhang | Balancing accuracy and parsimony in genetic programming[END_REF], [START_REF] Luke | Lexicographic parsimony pressure[END_REF], [START_REF] Nordin | Complexity compression and evolution[END_REF]). Another remarkable fact in favor of GP is that the simulation time is unavoidable for optimizing the relevant class of fitnesses.

This only concerns the general framework of designing Turing-computable functions. Of course, on restricted framework, automatic programing e.g. from specifications is possible.

  and almost surely the time complexity per value of m is O(L(m)).

Lemma 13 (

 13 Adapted strong law of large numbers): 1. Define L(m) → ∞ as m → ∞. Assume that x is a non-negative random variable with finite expectation. Then e m = 1 m m i=1 min(x i , L(i)) → Ex, if the x i are an iid sample with the same law as x. 2. Assume that x has infinite expectation. Then e m = 1 m m i=1 min(x i , L(i)) → ∞. Proof of 1 (2 is similar): Step 1: upper bound. e m ≤ m m = 1 m m i=1 x i and by the strong law of large numbers from Kolmogorov the right term goes to Ex.

  , y 1 , . . . , x m , y m > and where g(< x 1 , y 1 , . . . , x m , y m >) is itself a Turing machine.

	• Consider	g, a	function taking as	input
	<	x 1

• Then, the so-called error rate of g after m examples (x 1 , y 1 ), . . . , (x m , y m ) is the probability for P (x, y) of g(< x 1 , y 1 , x 2 , y 2 , . . . , x m , y m >)(x) = y. It is a random variable, as it depends on the m first examples. Statistical learning theory is the study of properties of various functions g, depending (or not) upon properties of P .

  The main drawback of GP is that GP is slow ; one can not get rid of the computation time. In theorem 15, using a modified form of Kolmogorov's complexity, we have shown that getting rid of the simulation time is anyway not possible. The summary of this paper, which is relevant for the research of Turing-computable functions realizing a given mapping, is as follows:

				Programming
				progs
		finite-time		other inf.	iterative
		progs		time progs ?	progs
	size fitness	speed fitness	space fitness	size fitness	speed fitness
	uncom -putable (cor. 3)	uncom -putable (cor. 2)	uncom -putable (cor. 5)	generalizes well (th. 10)	does not generalize (remark 9)
			uncom-putable (th. 8.b)	slighly faster ?	much faster simulation than	s
					uncom
					-putable (th.
					15)
	• in theorem 12, we have shown that an iterative
	programming-program could asymptotically perform
	the required target-task. E.g., GP is such an iterative
	method. Theorem 8 also shows that mixed fitnesses
	should be used ; this is very related to bloat, a well
	known problem in GP: without parsimony pressure, very
	long programs appear and the optimization does not
	work.
	• GP is simulation-based and many GP-applications use
	fitnesses as required according to our results, i.e. mixing
	both size and precision.

•

Here, a configuration is the current state plus the state of the internal tapes.


Regina Bernhaupt
email: regina.bernhaupt@irit.fr

Michael M Pirker
email: michael.pirker@ruwido.com

Antoine Desnos
email: antoine.desnos@irit.fr

Keywords: 3D User Interface, soap bubbles, IPTV Systems

Media consumption in the IPTV sector has changed over the past years and decades. It evolved from a linear viewing behavior on just one device, the TV with a few channels, to a connected home entertainment environment with multiple screens. Also user interfaces need to adapt to these new requirements and ensure a good user experience and meet the consumers' needs for natural, straightforward and pleasant method of interacting with their IPTV systems. We have developed a new kind of user interface as a tailor-made alternative to current list or grid menus in order to not only address current limitations of list and grid menus, but to offer a novel and unique way to interact with TV content that makes using an interactive system an event again.

Introduction

A large variety of functionalities and an almost endless amount of content is available for today's IPTV users. This development is a consequence of changes in media consumption, which altered from a linear viewing behavior on just one device -the TV -to a connected multi-screen home entertainment environment.

In order to keep up with this development, also user interfaces need to adapt to these new requirements and support the users with easy and intuitive menu structures. At the same time, those menus should offer interaction mechanisms that can deal with this variety of content and functionality. TV user interfaces and their input devices have to ensure a good user experience and meet the consumers' needs for natural, straightforward and pleasant method of interacting with their IPTV systems. Keeping in mind the increasingly complex TV ecosystem, our research goal was thus to provide a tailor-made alternative to current list or grid menus that provides an easy and intuitive way to navigate in large quantities of content items. Furthermore, it should improve the currently existing interface design metaphors and enable the user to engage with their TV services in a novel and playful way, improving the overall user experience. In order to address our research goal, we have developed a new kind of user interface in order to not only address current limitations of list and grid menus, but to offer a novel and unique way to interact with TV content that makes using an interactive system an event again. To follow up this increasing amount of content and functionalities, IPTV user interfaces have become increasingly complex and cluttered. As shown in Figure 2, while focusing on the information to be displayed, they are forgetting their primary goal: allow the user to enjoy watching television.

As every user interface needs an interaction mechanism, these cluttered user interfaces often come along with a complex, unappealing and bulky remote control that often makes the activity of watching television a painful task. Finally, one common issue in IPTV graphical user interfaces is that they present complex information in a very abstract way, using endless variations of grid-based user interfaces.

Can an interactive user interface present numerous and complex information in a more tangible way, closer to the user's mood of watching his TV content? To answer this question we decided to propose a new consistent TV ecosystem, including the graphical user interface (GUI), the remote control (RC) and the set-top-box (STB). Based on previous studies [1] we started the iterative design process of the GUI concept. The design propositions were evaluated by an expert to match the user's needs and the aesthetic goals which led us to a first version of the Bubble User Interface concept, a dynamic alternative solution in representing IPTV contents that brings the pleasure of watching TV back to the user (Figure 1). Subsequently, we started the implementation of the prototype while iterating the design aspects, leading to a second version of the Bubble User Interface that we present in this paper. The RC and the STB were then designed and built to match the GUI concept, in order to perform future user tests.

A real-world visual metaphor to break with cluttered interfaces

The concept of the Bubble user interface consists in mapping to an abstract content (IPTV information) a tangible, non-cultural oriented material that everyone can recall (soap bubbles). The goal is to implicitly add a feeling of lightness and clarity to the information in a way that a user would enjoy interacting with, while keeping the overall consistency that a graphical user interface needs. To achieve this vision, we used the visual metaphor of soap bubbles and included it as a primary component of the user interface, applying its physical properties and embodied meanings to the representation of the information. The fact that soap bubbles are multiple, numerous objects, while being physically the same allowed us to use it as a primary component of an interface, ensuring consistency through the different parts of the interface. Each piece of information is encompassed into one soap bubble, giving it a familiar texture that would help the user to interact with.

Shaping soap bubbles to IPTV content additionally gave us the possibility to provide a solution for every kind of TV display (stereoscopic and non-stereoscopic), and to take advantage of the third dimension to display the large amount of content that IPTV systems require. Furthermore, they are transparent objects, which allowed us to avoid the recurrent problem in 3D UIs [2] that they quickly appear to be very clumsy and not easy to use, especially in dense environments.

Although we solved the problem of item selection in a dense 3D environment by dedicating an area of the screen to the selection process, the transparency of the soap bubbles allows the user to preview further items in the interface and thus anticipate his selection process (Fig. 3.).

This also allowed presenting a large amount of content available on sight for the user, while keeping the desired concept of clarity and clearness. Yet, in order to lower the cognitive load of the user, only the first seven items are clearly readable.

Semiotic of soap bubbles

Soap bubbles could stand for a visual definition of lightness, clarity and enjoyment, all meanings that fit our goal to provide not only simple, easily understandable information but also a playful and pleasant interaction.

As stated by Cox [3], the visual juxtaposition of two different elements engages the cognitive process of mapping the properties of one (the source domain) to the other (the target domain). When confronted to IPTV contents (target domain) encompassed into soap bubbles (source domain), the user will map the physical properties of a soap bubble (lightness, airiness…) and some of his personal experiences (blowing a soap bubble, playing with it, having fun) to the IPTV content. By doing so, he is now able to reconsider his TV content and the numerous features that come along in a completely different way.

Several experiments have been made in terms of representation and interaction techniques, from mixing computed soap bubbles and the user's actions [4], to using real soap bubbles as an input to interact with interactive contents [5]. Soap bubbles are natural objects that are universally known. Their very specific nature has been of interest for both artists and scientists [START_REF] Emmer | Soap Bubbles in Art and Science: From the Past to the Future of Math Art[END_REF], and their physical properties can be experienced by anyone. This is an important point that a large majority of the users confronted to soap bubbles will instantly be able to identify a soap bubble and be able to predict or expect its behavior, just by recalling his personal experience.

A custom-tailor interaction mechanism

Alongside with the soap bubble metaphor used in the graphical user interface, a custom-tailored interaction mechanism has been designed to match the graphical user interface (figure 4), to keep the overall concept consistent and to better support the user's activity of watching television. This interaction mechanism allows the user to directly manipulate the soap bubbles in the synchronized user interface. Following the principles of simplicity of the user interface, the number of buttons on the remote control has been reduced to a minimum, favoring one central rounded input dedicated to the navigation, and offering a more analogue way to navigate through content. In order to closely follow the user's actions, this analog input is visually translated through the interface in a sequence of animations: rolling or moving the orb allows the user to move through the three dimensional interface either selecting or avoiding the soap bubbles on the screen.

To keep the overall concept consistent, the input device resembles a sphere and offers the opportunity to navigate within the dynamic user interface in an easy way. The tactile feeling of the input device allows a fast and intuitive navigation within the 3D UI and thus enables a playful and pleasant interaction experience for the user, giving him the possibility to move his point of view in the 3D space in order to browse the content.

Summary

Using the soap bubble visual metaphor to represent information allowed us to create a 3D interface that takes advantage of the third dimension to display a lot of information, while at the same time avoiding the issue of a cluttered environment by using the soap bubble's transparency property.

To keep the overall system consistent, we designed an interaction mechanism that matches the user interface to facilitate the user's interaction with the system. We lowered the number of keys to reduce the user's cognitive load, while a proper mapping of analog inputs in the user interface allows a more sensible and playful way to interact with the system. Finally, the use of the visual metaphor of soap bubbles allows to implicitly applying the embodied meanings of airiness, clarity and playfulness to the complex information presented by the system, bringing back the pleasure of watching TV into the living room.

Figure 1 .

 1 Figure 1. The Bubble User Interface, the matching Remote Control and Set-Top-Box

Figure

  Figure 3. Using the visual metaphor to represent the different elements and content of the user interface

Figure

  Figure 4. The interaction mechanism, designed to match the user interface and thus providing a consistent solution


G Fromentin

G Poulachon

A Moisan

B Julien

J Giessler

Precision and surface integrity of threads obtained by form tapping

Keywords: Cold form tapping, Surface properties, Assembly

Largely applied to internal threading of extruded tubes, cold form tapping is now becoming a promising process for internal threading of holes in non ferrous and ferrous solid components, more particularly for mass production in the automotive industry. The aim of this study is to present the surface properties of the threads resulting from form tapping. Geometrical characterization, surface texture, mechanical and metallurgical observations are investigated. The results obtained are discussed according to the input parameters of the process, and are compared to those obtained from cut tapping. The strength of the work material and the influence of the lubricant are the two main parameters affecting the process, and a correlation with the tapping torque is proposed. Finally, the characteristics of the thread surface depend on the parameters of the tapping operation, thus it has to be taken into account in the design approach when this tapping process is chosen.

INTRODUCTION

The threaded joint is one of the most widely used solutions for assembling mechanical parts, because it leads to an assembly having a high strength and high rigidity. Moreover the use of thread allows disassembly for maintenance and recycling. Concerning the manufacturing of internal threads or nuts, two main processes are available: cut tapping and form tapping. The choice of one of these processes has to result from considerations including process aspects, and also from an analysis of the specifications and characteristics of the internal thread. Form tapping is a different process from cut tapping for obtaining internal thread. Cut tapping is a machining process, the thread results from chip removal. In the case of form tapping, the thread is formed only by the displacement of the work material. A new growth of interest in this technique is obvious in the metal forming industry, and in particular in the automotive industry, due to the advantages inherent to the process itself: a higher number of tapped holes during the tool life, minimum quantity of lubricant, better reliability, better cleanliness (no chips). The thread obtained by form tapping is characterized by the appearance of a split crest at the top of the thread, as shown in Figure 1. Its rate of formation, as it was shown by S. Agapiou [START_REF] Agapiou | Evaluation of the effect of high speed machining on tapping[END_REF], depends on the hole diameter before tapping. The smaller the hole diameter is, the smaller will be the split crest at the top of the thread after the form tapping operation. This forming process is available both with high ductile alloys such as non ferrous metals [START_REF] Agapiou | Evaluation of the effect of high speed machining on tapping[END_REF][START_REF] Ivanov | Rolling of internal threads: Part 1[END_REF][START_REF] Chowdhary | Modeling forces including elastic recovery for internal thread forming[END_REF][START_REF] Chandra | Forming taps and their influence on production[END_REF], and also with hardened steels as shown by [START_REF] Fromentin | Thread forming tapping of alloyed steel[END_REF][START_REF] Fromentin | Metallurgical aspects in cold forming tapping[END_REF]. Analytical models of this forming process have been proposed by S. Chowdhary [START_REF] Chowdhary | Modeling forces including elastic recovery for internal thread forming[END_REF] and by W.E. Henderer [START_REF] Henderer | Theory of the cold forming tap[END_REF]. So far, only a few studies have been carried out on form tapping, and most of them deal mainly with process aspects, without linking characterization of the formed thread. It is probably because the technical specifications for tapped holes are coming from characteristics of cut threads. The present study deals with the characterization of the internal thread obtained by the form tapping as a function of two process parameters: the lubricant, and the holder.

Different properties are analyzed: geometrical precision, metallurgical aspects, and mechanical properties. A comparison with cut tapping is conducted.

GEOMETRICAL CHARACTERIZATION

Geometric precision is one of the most important characteristics of the thread to guarantee a functional assembly. Two properties are analyzed: pitch error and flank straightness. Threads are measured with a mechanical stylus having a radius equal to 25 μm and using a 3D surface measuring instrument.

Thread pitch deviation

On first sight, the thread quality depends mainly on tap runout during machining, which leads to a pitch error. When a rigid holder is used, the occurrence of a Split crest synchronous error, between the linear motion and the rotation linked by the tap pitch, leads to an increasing of thrust force on the tap and on the workpiece. But, if a floating holder is used, the synchronous error is absorbed by a compression of the holder spring having a very low stiffness compared to the previous holder, and a lower force is transmitted to the tool as shown on Figure 2. Figure 3 shows the pitch error along the thread. The worst pitch is always the first one, whether the thread is obtained by cutting or forming. There is inevitably an error on the feed control of the tool during the entrance in the workpiece. The cut tap makes pitches which are too large (the error is positive), because it has right spiral flutes, then the axial force on the tool is in the feed direction, and the tap runs out. In the case of form tapping, the axial force is in the opposite direction, and the tool does not make too large pitches. The use of a rigid holder decreases the cutting tap runout, thus reducing the pitch error by half. But in the case of form tapping, this holder can bring about an error on the first pitches due to significant forces caused by the tool entrance in the workpiece. Except for this point, the use of form tapping leads to a lower and constant error on the thread pitch compared to the case of cut tapping.

Flank straightness

Another geometric property needed for a tapped thread is the straightness of its flanks to assure the contact with the screw. From the scanned thread profile used for the measurements of the pitch deviation, each flank is identified and the straightness is calculated after considering a least square line as shown in Figure 4. Figure 5 shows the flank straightness of cut and formed threads. Cut threads also have a lower quality regarding the straightness criteria. The first pitch is again the worst because of tool feed control during entrance, as already explained, and the use of a rigid holder contributes to reduce this error. The flank straightness deviation of formed thread is between 1 μm and 4 μm, which shows the accuracy of threads obtained by forming. The flank straightness deviation of those tapping by cutting, it is alternatively around 5 μm and 20 μm. The flanks having the worst straightness are those oriented toward the bottom of the hole. This can be explained by the pulling force on the holder after spindle reversing and when the cutting tap goes out of the workpiece. Thus, the cutting edges of the tool are in contact with these flanks and may damage them during the back travel of the tool. In the case of form tapping the tool does not have any cutting edge and there is only friction between it and the thread during the back travel. Consequently, the type of holder does not influence the flank straightness of threads produced by form tapping.

SURFACE INTEGRITY IN FORM TAPPING

Strain hardening on thread

The use of form tapping leads to plastic flow of the work material when making the thread. No metallurgical transformation is observed, nevertheless this process necessarily involves a strain hardening of the material constituting the thread. This strain hardening is quantifiable by microhardness measurements. Figure 6 shows measurement profiles at the root of the thread which appears to be the most deformed zone inside the thread. The initial hardness of the work material is 285 HV, and the hardness at 15 μm from the root is around 540 HV when the emulsion is used for tapping. In this case it represents an increase of 90% in hardness. Moreover, the hardness measured directly on the flank of this thread is 770 ± 30 HV. This value is comparable to the hardness of the HSSE substrate of the form tap, which involves that the coating on the tool is essential for form tapping high strength steel. By using the oil, which is a much better lubricant compared to the coolant according to a lower tapping torque (26.3 N.m against 41.7 N.m), the strain hardening appears also to be considerably reduced as shown Figure 6. Figure 6: Strain hardening at the root of formed thread. These hardness measurements show that the thread obtained by form tapping undergoes a high strain hardening and there is a strongly deformed layer at the thread surface. This deformed layer is largely influenced by the intensity of the friction between the thread former and the work material. As a consequence, the lubricant has a prime importance on thread characteristics. The strain hardening would raise the strength of the thread. The drawback is that this hardening has necessarily an effect on wear of the form tap, which would be considerably reduced by using an efficient lubricant.

Residual stresses and metallurgical texture on the thread flank

First of all, using a SetX device, residual stress measurements by X ray diffraction are conducted on the flank which is the largest area of the thread. The {211} planes of the ferritic phase are used for the diffraction. Despite a long time of exposure, the intensity of diffraction peaks is not sufficient to measure residual stresses with a good accuracy, the area of the diffracted surface being too small. The results on the flank of the thread tapped with the oil are shown in Table 1. 1: Residual stress on the flank of the thread tapped with oil (r: radial direction / θ: tangential direction). Despite poor precision, it shows that the residual stresses in the radial and tangential direction, σ rr and σ θθ , are compressive stresses which would be favourable to fatigue life of the thread. Concerning the shear stress, σ rθ , it is zero, and it would be linked to the efficiency of the oil used. In order to identify the material texture, Electron Back Scattered Diffraction (EBSD) technique is used rather than X ray diffraction which needs a larger surface and limits the incidence angle during analysis. The surface analyzed needs to be prepared by mechanical-polishing and electrochemical-polishing. As a consequence, it is the subsurface which is measured and not exactly the surface itself, on which residual stresses are measured. Figure 7 shows the {100} pole figures on the raw material, i.e. before tapping, and on the flank of the thread tapped with oil. Initially, the work material is little textured; the intensity does not increase over 3. Three poles at 90° can be seen on Figure 7(a), meaning there is only one texture. This texture is probably linked to the hot rolling and recrystallization of the raw material. After tapping, Figure 7(b) shows that the material is quasi isotropic. In conclusion, form tapping of a ferrito-perlitic steel induces compressive stress and the plastic flow tends to reduce initial texture of the work material.

Stress

MECHANICAL ASPECTS

Several considerations may concern the mechanical properties of threads. In this study, only two characteristics are investigated: the friction between the threaded holes and screws, and the ultimate strength of the tapped threads.

Friction

The friction coefficient between the flanks of the internal and the external thread needs to be known in order to determine the tightening torque to guarantee a functional assembly. If the friction coefficient between the threaded surfaces is overestimated, then the tensile force inside the screw will be too high. As a consequence, the screw may break, or the threaded hole may be damaged or both. On the opposite, if the friction coefficient is underestimated, the tensile force will be too low, and then it will not guarantee the assembly. A special device has been designed in order to measure directly the tightening torque without being influenced by the friction under the screw head. Dry friction conditions are obtained by cleaning threads with solvent and using ultrasonic chatter. No agent is used to lubricate the threads during tightening. Several threaded holes having different characteristics are tested. After tapping, sulphur coming from oil is measurable on the flank surfaces of the formed thread by EDS analysis (Electro Dispersive Spectrum). This occurrence of sulphur characterizes a tribological layer caused by the chemical reaction between the oil additives and the worked steel. This tribological layer leads to reduced friction during tapping. There is no layer on a formed thread with emulsion, which explains the lack of lubricating action of this fluid characterized by a higher torque during tapping and a higher strain hardening (cf. § 3.1). Cut threads are machined with the same oil that is used for obtaining formed threads. Nevertheless, there is also no tribological layer on the flank surfaces of these cut threads, showing a different lubricating action of the oil than in form tapping. Figure 8 summarizes results of tightening tests. Despite these differences on the flank surfaces, it is difficult to identify a significant effect on the value of the friction coefficient. The measurement dispersions are too large compared to the difference between the three types of threads. The dispersion is particularly important for threads formed with oil. The friction coefficient may be included in a range from 0.2 to 0.43. Thus, the friction coefficient may be lower or higher than in the case of a cut thread which has the worst flank straightness. These results are also influenced by the variation of characteristics of the screws used for the tightening tests. No attention has been paid to them except their geometrical quality class which is the same than those of the threaded holes: 6h. Screws are produced in mass production by rolling process, and there is chance of damage due to impact. threads. From an industrial point of view, when there are many variations on the machining process, on the screws, and on the tightening process, the conclusion is that formed threads have to be considered as being identical to cut threads relatively to the tightening torque.

Thread strength

The basic property of thread holes is their strength. Quasi static tensile tests are conducted to quantify and to compare the characteristics of threads obtained by cut tapping and by form tapping. For this goal, fracture of the internal thread has to be realized without the failure of the screw. Such comparison tests may not be done with the C70 carbon steel used for all the previous characterizations. It has an ultimate stress equal to 900 MPa and with high strength screws (1080 MPa), the screw will also be damaged during tensile tests. Consequently, threaded holes are produced in a C22 low carbon steel (540 MPa) for making these characterizations. The strength of the tapped hole material being half the strength of the screw, the fracture of the internal thread will be caused without external thread damage, according to the analytical predictive model of E.M. Alexender [8]. The thread length between tapped hole and screw is fixed to 3 mm, i.e., two pitches, for the breakage tests. Figure 9 shows the ductile rupture features obtained in the case of a C22 cut thread.

Figure 9: SEM picture of fracture pattern on cut thread. Figure 10 sums up the results of tensile tests. Despite the split crest, the strength increases by 27% by using the form tapping process in C22 steel. The uniform shear stress increases from 270 MPa to 380 MPa. This gain is attributed to the strain hardening induced inside the thread during form tapping (cf. §3.1). The value of the maximum tensile force given by the Alexander model is between those measured with the cut and the form thread. With C70 threads, an increase of strength can not be characterized with 1080 MPa screws. Thus, form tapping is not motivated by increasing strength of this assembly, but it would be by other properties of the process, or of the threads produced.

CONCLUSION

The major property of formed threads, in the case of steels, is the high strain hardening, which results from the plastic flow under very severe friction conditions at the interface with the tap, and leads to a strongly deformed layer at the thread surface. The lubricating effect of the tapping fluid is a preponderant operational parameter. It considerably influences the increase in hardness and in thickness in the deformed layer and it also influences on the tool damage and wear. Nevertheless, the strain hardening is responsible for an increase in formed thread strength under static force, compared to those obtained by cut tapping. Residual stresses in the deformed layer are compressive due to the predominance of their mechanical origin, which would increase fatigue strength. The second dominant property of formed threads is the geometrical quality which is much better compared to those obtained by cutting. Moreover, the tightening torque is unchanged by using form tapping, which facilitates the change of the cut tapping to the form tapping. Form tapping performance has been established on process aspects as well as on thread characteristics, and this process would be an alternative to cut tapping.

Figure 1 :

 1 Figure 1: M12×1.5 formed thread in C70 steel. Tests are conducted with a DMC65V 3 axis machining centre equipped with a vertical spindle controlled both in speed and in position. Blind holes are tapped either with a rigid or with a floating holder. The taps used are M12×1.5 6HX cut tap or thread former, made of sintered HSSE and TiN coated. Their design is composed of 3 flutes for the cutting tool, and 5 lobes on the forming tool. They have a short entry taper with 3 pitches. Two different fluids are used for tapping. The first fluid is an oil containing additives based on sodium sulfonates. The second is a 5% water based emulsion. The work material used is a C70 carbon steel. It has a ferrito-perlitic structure and its ultimate strength is 900 MPa.

Figure 2 :

 2 Figure 2: Thrust force and torque during tapping.Figure3shows the pitch error along the thread. The worst pitch is always the first one, whether the thread is obtained by cutting or forming. There is inevitably an error on the feed control of the tool during the entrance in the workpiece. The cut tap makes pitches which are too large (the error is positive), because it has right spiral flutes, then the axial force on the tool is in the feed direction, and the tap runs out. In the case of form tapping, the axial force is in the opposite direction, and the tool does not make too large pitches.

Figure 3 :

 3 Figure 3: Pitch error of cut and form thread.The use of a rigid holder decreases the cutting tap runout, thus reducing the pitch error by half. But in the case of form tapping, this holder can bring about an error on the first pitches due to significant forces caused by the tool entrance in the workpiece. Except for this point, the use of form tapping leads to a lower and constant error on the thread pitch compared to the case of cut tapping.

Figure 4 :Figure 5 :

 45 Figure 4: Flank straightness of a cut thread.

Figure 7 :

 7 Figure 7: {100} Pole figures measured by EBSD.

Figure 8 :

 8 Figure 8: Friction coefficient between internal and externalthreads. From an industrial point of view, when there are many variations on the machining process, on the screws, and on the tightening process, the conclusion is that formed threads have to be considered as being identical to cut threads relatively to the tightening torque.

Figure 10 :

 10 Figure 10: Thread strength under tensile force.