CODEWITHSUNDEEP
integer-divisionturing-machines
Panagiotis Iatrou
Panagiotis Iatrou

Reputation: 160

How to design a Turing machine for division of two numbers?

The machine takes 2 natural numbers (a, b) as input in unary form and outputs the integer quotient and the remainder of the integer division a / b. What would the initial and final state on the tape be? What would the functionality diagram look like?

Thanks in advance.

Upvotes: 4

Views: 11810

Answers (1)

Patrick87
Patrick87

Reputation: 28332

A design to use here is the following:

  1. cross off b instances of 1 from the part of the tape representing a, and increment a new part of the tape representing the quotient q each time you do it.

  2. if you ever have more 1s in b than you have remaining in the part that used to represent a, stop dividing; the symbols remaining represent the remainer and whatever your current quotient is, that's the answer

An implementation might do the following:

  1. take the input as #11...1011...1# where the first string of 1s represents a in unary, the second string represents b in unary, # is a blank and the tape head initially starts on the leftmost 1;

  2. immediately go write a Q at the end of the tape; anything after this is the quotient

  3. check whether b > a; if so, run some routine to rewrite the quotient and remainder in a pretty format before terminating. check by bouncing back and forth across the 0 and temporarily marking pairs of cells, then change them back to 1s afterwards.

  4. otherwise, change the b leftmost instances of 1 to X, go add a 1 after the rightmost 1, and then repeat from step 3. Mark off the b instances by bouncing back and forth across the 0 and temporarily marking the 1s comprising b so you don't double count; then, change them back to 1s.

Example:

initial tape: #11111011#
after step 2: #11111011Q#
after step 3: (same)
after step 4: #XX111011Q1#
after step 3: (same)
after step 4: #XXXX1011Q11#
after step 3: #1101# (formatted)

Upvotes: 1

Related Questions