Task Systems A "task system" is defined to be a triple S = (Q,T,cost) where Q is a set of states, T is a set of tasks, and cost(q,t,r) is defined to be the cost of serving task t while moving from state q to state r. We allow a value of the cost function to be infinite, indicating that that movement is not allowed. One state is designated to be the start state. We say that a task system is "finite" if both Q and T are finite and if the value of cost is always an integer or infinite. A finite task system is thus an NFA with input alphabet T, where each transition has an integral cost. We say that S is "complete" if cost(q,t,r) is finite for all q, r, and t. We say that S is "non-trapping" if, for any q in Q and any t in T, there is some r in Q for which cost(q,t,r) is finite. We say that S is a "metrical task system" if Q is a metric space with integral distances, and if there is a function f(t,r) such that cost(q,t,r) = |q,r| + f(t,r) for all q, t, and r. A "task sequence" (also called "request sequence") is a string over T. A "service" of a given task sequence is defined to be a valid computation of the NFA with that input string. The cost of a service is defined to be the sum of the costs of the transitions. For a given task sequence, the optimal cost is defined to be the minimum cost of any service of that task sequence. Let S = (Q,T,cost) be a finite task system. We say that O = (W,T,optcost) is an "optimizer" for S if: (a) O is a finite task system. (b) O is deterministic, that is, for any w in W and any t in T, there is at most one x in W such that optcost(w,t,x) is finite. (c) Given any task sequence sigma, there is at most one valid computation of sigma in O which uses no edges of infinite cost. The cost of this computation is equal to the optimal cost of sigma in S. Theorem 1: If a finite task system has an optimizer, it has a unique minimal optimizer. Theorem 2: Every finite metrical task system has an optimizer. Theorem 3: Every complete finite task system has an optimizer. Conjecture: Every non-trapping finite task system has an optimizer.