Efficient Computation by Three Counter Machines Holger Petersen Reinsburgstr. 75 70197 Stuttgart 5 1 Germany 0 2 January 12, 2015 n a J Abstract 9 Weshowthatmultiplicationcanbedoneinpolynomialtimeonathree ] counter machine that receives its input as the contents of two counters. C The techniqueis generalized tofunctions of two variables computable by C deterministic Turing machines in linear space. . s c 1 Preliminaries [ 1 In an investigation of the power of simple counter machines [1], Schroeppel v 2 described a four counter machine that multiplies two numbers in quadratic 1 time and posed as a hard problem to multiply two numbers using only three 2 counters. Hepresentedasolutionbasedonanexponentialencodingofnumbers 2 and asked whether there is a way that takes less time. 0 The purpose of this note is to firstpresent a solutionfor multiplication that . 1 runs in time polynomial in the maximum input value and then generalize the 0 technique toalltwovariablefunctions thatcanbe computedbyadeterministic 5 Turingmachinesoperatinginlinearspace(linearboundedautomaton)towhich 1 : the arguments are passed in binary representation on its work-tape. This class v of functions includes integer division. i X A k counter machine is equipped with k counters each storing a nonnega- r tive integer. Its operation is controlled by a deterministic sequential program a consisting of four types of instructions: Increment: Add 1 to the specified counter. Conditional Decrement: If the specified counter stores a value greater than 0, subtract 1. Otherwise leave the counter unchanged and jump to a specified instruction out of the normal flow of control. Unconditional Jump: Flow of control is transferred to the specified instruc- tion. Halt: Stop execution. 1 Notice that unlike many computational models studied in Complexity Theory, acountermachinehasnoseparateinput-tapeoroutput-tapeandreceivesinput values as the contents of its counters, which corresponds to a unary encoding. Instead of breaking down an algorithm into these four basic instruction, we will use additional notation borrowed from higher programming languages. In thefollowingwesketchhowtosimulatetheseconstructswithmacrosoncounter machines. ByR,R1,R2wedenoteanyofthe firstk−1counters,whilecounter k is reserved as auxiliary scratch memory. Counter k is assumed to have 0 as its initial value and all macros will restore this value. if R > 0 then begin...end: Decrement R and jump to the instruction after end if R was 0 before the instruction. Otherwise increment R (restoring its valuebefore the if)andcontinue withthe instructions betweenbegin and end. while R > 0 do begin...end: Like if R > 0 then... described above, but jump back to the decrement instruction before the end. if odd(R) then begin...end: In a loop decrement R twice while increment- ing counter k. If R has the value 0 in the first decrement instruction, its inital value was even. Then restore its value by incrementing R twice whiledecrementingcounterk. Skipthebegin ...endblock. IfRhasthe value0intheseconddecrementinstructionoftheloop,itsinitalvaluewas odd. Restoreits valueasinthe casewhenits valuewaseven,additionally adding 1. Execute the instructions between begin and end, while even(R) do begin...end: Like if odd(R) then... described above (roles of odd/even interchanged), but jump back to the test before the end. R1 := R2: In a loop decrement R1 until it is 0. In another loop decrement R2 whileincrementingR1andcounterk. Finallyinaloopdecrementcounter k and increment R2, restoring its previous value. R1 := R1 + R2: InaloopdecrementR2untilitis0whileincrementingR1and counter k. In another loop decrement counter k and increment R2, thus restoring its previous value. R1 := R1 - R2: Ina loopdecrementR2 until it is 0 while decrementing R1 (if possible) and incrementnig counter k. In another loop decrement counter k and increment R2, thus restoring its previous value. Note that if R1 < R2,theresultingvalueofR1willbe0. Thisoperationissometimescalled modified minus. R := m * R: In a loop decrement R while incrementing counter k. In another loop decrement counter k and increment R in every iteration m times. R := R div m: InaloopdecrementRwhileincrementingcounterk. Inanother loopdecrementcounterkmtimesandincrementRforeveryfulliteration. 2 2 Results Proposition 1 A three counter machine can compute X ∗Y for nonnegative integers X and Y in polynomial time as the contents of a counter when X and Y are initially stored in two counters. Proof. The algorithm will be presented using the macros introduced above: procedure mult; (* input: X in A, Y in B; output: B *) begin if B > 0 then (* special case Y = 0, output Y *) begin A := 2 * A + 1; (* flag in lowest bit *) (* Loop I *) while B > 0 do begin A := 2 * A; if odd(B) then begin A := A + 1 end; A := 2 * A; B := B div 2 end; B := A; A := A + 1; (* flag in lowest bit *) (* Loop II *) while even(B) do begin A := 2 * A; B := B div 4 end; B := B - 1; (* remove flag *) (* Loop III *) while even(A) do begin B := 8 * B; A := A div 2 end; A := A - 1; (* remove flag *) (* Loop IV *) while even(A) do begin A := A div 2; B := B div 4; if odd(A) then begin A := A + B end; A := A div 2; B := B div 2; end; A := A - B; (* adjust initial value of A *) B := A; B := B div 2 (* remove flag *) end end; (* mult *) 3 In the following the purpose of the four loops is outlined: Loop I: For each bit d of B (input Y) shift two bits d0 into A, thus reversing the order of bits. Loop II: Eachtwo-bitgroupgeneratedinloopIistranslatedinto0andshifted intoA.AttheendofloopIIcounterAcontains(startingfromlowestbits) log (Y+1)0-bits,2log (Y+1)groupsoftwobitseachcontainingasingle 2 2 bit of Y in the higher order bit, a single 1 and the input X shifted by 3log (Y + 1)+ 1 positions. At the end of loop II counter B contains 2 2Y+1. Loop III: B is shifted by 3log (Y+1) positions, while the trailing 0-bits are 2 removed from A. Loop IV: Add the multiples of X stored in B to an ‘accumulator’ in A with initial value Y. In addition, A stores the two-bitrepresentationof X. It is decoded and controls the additions. 3 NoticethatthemaximumvaluehandledbythealgorithmisoforderX∗Y . The macros introduced are time-bounded by this value and the loops of the main algorithm are executed log (Y+1) times. Thus the running time of algorithm 2 is polynomial in the input values. ✷ Theorem 1 Theclassoffunctionsoftwovariables computablebythreecounter machines in polynomial time coincides with the class of functions of two vari- ables computable by deterministic Turing machines in linear space, where input and output of the Turing machines are encoded in binary. Proof. We first show how to simulate a Turing machine efficiently with the helpofathreecountermachine. Givenaconciseencodingofthe inputitiswell known how to do this (see, e.g., the Theorem on p. 2 of [1]). Thus we will only sketch this part and focus on the input- and output-problem. Let Turing machine M computing function f(x,y) have the tape alphabet Σ that includes a blank symbol, symols 0, 1 and a separator #. We assume thatthe inputis encodedasbin(x)#bin(y)R (where wR isthe reversalofstring w), M starts its operation with its tape head before the first symbol of bin(x), and M stops with bin(f(x,y)) as its tape contents with its head again before the first symbol (the simulation can easily be adopted to other input-/output- conventions). A three counter machine C simulating M has x on counter 1 and y on counter 2. For encoding M’s tape alphabet C reserves k = ⌈log |Σ|⌉ bits per 2 symbol and uses the following codes for M’s symbols: blank: A sequence of k zeroes (this in mandatory,since the infinite number of blank symbols is represented by counter value 0). #: The sequence 0k−11. 0, 1, and further symbols: Sequences 0k−210, 0k−211 and so on. 4 First C computes 2kx + 1 (thus encoding a separator) and then (using counter 3 as scratch memory) repeatedly divides counter 2 by 2 and multi- k plies counter 1 by 2 adding the appropriate constants encoding 0 and 1. This process continues until counter 2 is 0. In the next loop C decodes k bits from counter counter 1 and puts the encoding on counter 2 until the encoding of separator # has been transferred. Notice that the least significant bits of y are encoded in the least significant k-bit blocks. Finally the analogous process is carried out for x, putting the blocks onto counter 2. After this preparation, C carries out the standard simulation of M treating blocks of k bits as an encoding of symbols from Σ. When M stops, C translates the encoding back to a number stored on counter 1 by reversing the encoding outlined above. Since all numbers can beencodedinO(logx+y)bits,thesimulationispolynomialintheinputvalues For the simulation of a polynomial time k counter machine by a Turing machine observe that due to the limited arithmetic the numbers generated on the conuters are polynomial and can be encoded in linear space. Therefore a Turing machine cansimulate the counter machine by updating k binarystrings representing the counter contents. ✷ References [1] R. Schroeppel. A two-counter machine cannot calculate 2N. Technical Re- port 257, Massachusetts Institute of Technology, A. I. Laboratory, 1973. 5