Jump to content

convert a turing machine to oblivious turing machine

Praveen2710
in Homework Help

Featured Replies

Hi

I have an assignment question which I have no clue on how to start.I am posting the question. I would really appreciate if someone could guide me on how to solve it.

 

Question:

  1. Show that for every time-constructible T: N → N, if L ∈ DTIME(T(n)), then there is an oblivious TM that decides L in time O(T (n) log T (n)).

Any material that will help solve it or any similar examples would be highly appreciated.

Archived

This topic is now archived and is closed to further replies.

Go to topic listing

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.

Configure browser push notifications
Chrome (Android)
  1. Tap the lock icon next to the address bar.
  2. Tap Permissions → Notifications.
  3. Adjust your preference.
Chrome (Desktop)
  1. Click the padlock icon in the address bar.
  2. Select Site settings.
  3. Find Notifications and adjust your preference.