CODEWITHSUNDEEP
algorithmcomputer-sciencedfaturing-machinesnon-deterministic
Alyssa Buchthal
Alyssa Buchthal

Reputation: 67

A turing machine that decides {0^2^n; n>0} that's not the commonly accepted one

We're being asked to create a Turing Machine that accepts {0^(2^n); n>0} that is not the commonly accepted one published by Michael Sipser.

Sane Turing Machine

Instead, we are being asked to create one for the algorithm as follows:

It will continue in such a fashion, crossing out as many zero's in each pass as were crossed out in all the previous passes combined (1, 1, 2, 4, 8, 16, etc.), until there are no zero's remaining and none to be crossed out (accept) or there are no zeros remaining, but there were some remaining to be crossed out (reject).

Now my issue here obviously stems from the fact that Turing Machines do not store data values. While a Turing Machine can be used as a counter (enumerators), they cannot then store the value that was counted and act upon it. I have come up with several infinitely long, non-deterministic Turing Machines that employ this algorithm, but none that are deterministic. I am allowed to use as long of a write alphabet as is necessary.

Please do not ask me why I am being asked to create such a useless machine considering an efficient, simple algorithm is already available and widely known. I honestly couldn't tell you.

Upvotes: 5

Views: 14319

Answers (3)

trincot
trincot

Reputation: 350996

First on the TM pictured in the question:

  • It is the preferred approach, as it has a time complexity of O(𝑛log𝑛), while the algorithm you ask for will have a O(𝑛²) complexity (see below).
  • It accepts "0", while in the text you write that the language is 0^(2^n); n>0}, of which "0" is no member. Possibly you intended n>=0, as then "0" is a member. I will assume this in the rest of this answer.

The following TM will double the marked symbols in each outer cycle, extending to the right:

enter image description here

Each time the state transitions away from replace, the number of "1" is a power of two. The states read and carry accomplish the next doubling (zig-zag approach)

Here is the transition table in a snippet that can be run with the input of your choice:

createTuring({
    transitions: [
        { state: "start",  read: "0", write: "1", move: "R", nextState: "replace" },
        { state: "start",  read: "_",             move: "L", nextState: "reject"  },
        { state: "read",   read: "2",             move: "L", nextState: "read"    },
        { state: "read",   read: "1", write: "2", move: "R", nextState: "carry"   },
        { state: "read",   read: "_",             move: "R", nextState: "replace" },
        { state: "carry",  read: "_",             move: "L", nextState: "reject"  },
        { state: "carry",  read: "2",             move: "R", nextState: "carry"   },
        { state: "carry",  read: "0", write: "2", move: "L", nextState: "read"    },
        { state: "replace",read: "2", write: "1", move: "R", nextState: "replace" },
        { state: "replace",read: "0",             move: "L", nextState: "read"    },
        { state: "replace",read: "_",             move: "L", nextState: "accept"  },
    ],
    initState: "start",
    tape: "00000000",
});
<script src="https://trincot.github.io/turing.js"></script>

Because of the zig-zag that is needed during the doubling of the marked symbols (by marking with 1 and 2), each phase of doubling has a complexity of O(𝑘²) where 𝑘 is the size of the section that is being doubled (𝑘 is a power of 2). This leads to an overal time complexity of O(𝑛²).

Upvotes: 0

Sid
Sid

Reputation: 147

Turing Machine for L

I believe this is the most intuitive way of approaching the problem. The image above can be simplified as some transitions are redundant.

The common solution of crossing out alternative zeros, though simple, is not something all can think of.

Upvotes: 1

user58697
user58697

Reputation: 7923

A Turing machine can store values. To do that sometimes you need to play certain tricks. Given that you may use a large alphabet, do each pass like this:

  • At the beginning of the pass, the tape has a certain range of xs representing what has been crossed out, followed by a range of yet uncrossed 0s.

  • Find the leftmost x. Change it to y. Find the leftmost 0. Cross it out with z. Repeat as long as there are xs.

  • Go to the beginning of the tape, and change each y and z with x.

Prove that after such pass number of xs double, and implement the machine.

Upvotes: 1

Related Questions