0
$\begingroup$

Let $Q$ be the set of states of the Turing Machine, $\Sigma$ be the alphabet, and $\{L,R,S\}$ be the left shift, right shift, and stay respectively.

A transition is an element of $Q \times \Sigma \times Q \times \Sigma \times \{L,R,S\}$ which can be read as current state, current symbol, next state, next symbol, movement direction.

For a Turing Machine I'm looking to understand how many transitions, or states since they are linearly related, are needed so that when I give integer $i \ge 0$ on the tape it outputs the $i^\text{th}$ digit after the decimal point(zero indexed) of $\frac{p}{q}$ for which $p$,$q$ are coprime. Assume it is in base $c$ and you only have the characters $0,1,\dots,c-1$ and blank. I imagine this is possible to do in $O(c\log q)$ states, but my best attempts(outlined below) only give me $O(cq)$. An example where $c=2$ and $\frac{p}{q}=\frac{1}{3}$ would be I want a binary Turing machine such that when given $10$ on the tape would output the $3^\text{rd}$ digit after the decimal point of $\frac{1}{3}$ which is $0$ and when given $110111$ would output the $56^\text{th}$ digit which is $1$.

Here is my way of doing it. For the purpose of this $\text{nt}(c,q)$ is the length of the non-terminating portion length of $\frac{p}{q}$ in base $c$, this is easily verified to be the same for all coprime $p$,$q$. Also define $\text{per}(c,q)$ as the length of the periodic portion of $\frac{p}{q}$ in base $c$

My basic idea was you check if it is less than $\text{nt}(c,q)$ and if so output that digit and halt, this takes $O(c\,\text{nt}(c,q))$ transitions. If it's not smaller subtract out $\text{nt}(c,q)$ which takes $O(c\lfloor \log \text{nt}(c,q) \rfloor)$ transitions. Then test for what the result is modulo $\text{per}(c,q)$ and output the appropriate digit. This takes $O(c\,\text{per}(c,q))$ transitions. Now remember that the worst case of $\text{per}(c,q)+\text{nt}(c,q)$ is $q-1$. Therefore the final transition complexity is $O(cq)$

A second idea I had was Newton's algorithm which I think would take $O(c\log q)$ transitions. The basic idea would be to output $p$,$q$,$.1$ to the tape in base $c$, convert to unary which takes $O(c)$ transitions then do multiplication and subtraction in unary which takes $O(1)$ transitions. Would this work?

$\endgroup$
  • $\begingroup$ 1. I find your question hard to follow: "the tape" - what tape? are you asking about a Turing machine? "transitions" - please define what you mean by a transition. Please edit your question to be self-contained. 2. Ignore Turing machines for the moment, and imagine a real programming language. What's the best running time you know for division? Do you know how to do it in poly-log time? Hint: any such algorithm will lead immediately to a Turing machine. $\endgroup$ – D.W. Apr 30 '15 at 21:50
  • $\begingroup$ @D.W. I edited the question, hopefully it is easier to understand now. 2. Time complexity doesn't necessarily equal state/transition complexity though, at least I don't think so. $\endgroup$ – ruler501 Apr 30 '15 at 22:04
1
$\begingroup$

Using a Turing machine compiler I wrote I devised a program to do this in $O(c\log(q))$ transitions assuming $0 \le p < q$. More precisely it does it in $2 \lfloor \log_2(q) \rfloor +\lfloor \log_2(p) \rfloor + C$ states for some value $C$. I'm sure the value I found(~$409$) wasn't optimal.

The actual program itself is too long to include here(totaling $3584+18\lfloor\log_2(q)\rfloor + 9\lfloor \log_2(p) \rfloor$ lines) Here is the program in my pseudo language for approximating 5/9, it can be compiled with the program found here. The syntax for the language is also found there.

xn=1,4
while i decr {
    xnH=xn
    a=xnH
    a=a,0
    t=0,1
    while xnH decr {
        p=9,4
        while p decr {
            incr(a)
        }
        incr(t)
    }
    two=a
    two=two,2
    two=two,0
    first(two)
    while a decr {
        decr(two)
    }
    xnH=xn
    b=two
    b=b,0
    while xnH pop {
        b=b,1
        xn=xn,1
        incr(t)
    }
    pop(b)
    xn=xn,1
    while xn decr {
        p=two
        while p decr {
            incr(b)
        }
        incr(t)
    }
    xn=b
    incr(t)
}
xnH=xn
xnH=xnH,0
while xn decr {
    p=5,3
    while p decr {
        incr(xnH)
    }
    incr(p)
}
incr(xn)

xnH holds the final value(the whole thing is assumed to be after the decimal point). It shouldn't be too hard to extract out a single digit from it(in $O(1)$ states). Also as a note even for small values of i this program takes quite a long time to execute.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.