3
$\begingroup$

i'm trying to solve this question: Given a turing machine that is decidable by at most 50 * n^4 steps, can we build a dif algorithm that can decide it in n^4 steps?

Me and my friends thought about it, and we coulnd't get it right. Some points we had in mind: 1. if you can reduce the overall cost by 50 somehow, couldn't you reduce it over and over again? 2. we tried to think about algorithms that require 50*n^4 moves (at most) and we thought about this language: string str is in A if str.GetHashCode().GetHashCode()... 50 times is even. do you think this algorithm is unreducable?

thanks for the help!

  • 1
    Why did you down vote it? Its a pretty hard question..2011-02-28
  • 0
    It's not a good idea for the body of your question to be exactly the same as the title. It really makes it look like you haven't put in much effort to formulate a good question. Add to that the fact that this is obviously homework, and a lot of people are going to assume you copied it directly from your assignment. Put in some effort and show us what you've come up with on your own.2011-02-28
  • 0
    ok, i'll rewrite it2011-02-28
  • 0
    better? i really thought about it for a long time.. really non trivial one.2011-02-28
  • 0
    Your edit increased the quality of the question by at least 50 times. ;)2011-02-28
  • 0
    thanks. Now i hope i could talk with someone about it and understand how to answer it :)2011-02-28
  • 0
    Now that it's improved, I'm going to migrate it over to the [CS Theory](http://cstheory.stackexchange.com/) site where it belongs.2011-02-28
  • 4
    @Bill the Lizard, this is not research level question. Check [the speedup theorem on wiki](http://en.wikipedia.org/wiki/Speedup_theorem). Please do not migrate this kind of questions directly to cstheory, migrate them first to [Math.SE](http://math.stackexchange.com). cstheory is for *research level* questions. Thanks.2011-02-28
  • 0
    @Kaveh: Sorry about that. I forgot to read the FAQ before migrating. Thanks for the link, though. That should answer his question.2011-02-28
  • 0
    @Bill the Lizard, no problem. :)2011-02-28
  • 0
    @Adibe7, I think [the wiki page for linear speed-up](http://en.wikipedia.org/wiki/Linear_speedup_theorem) should answer your question, but if you want I can remigrate the question to Math.SE from here.2011-02-28

1 Answers 1

3

You can find the answer on Wikipedia. If you don't want to look it up, think how can you build a TM then executes $50$ steps of the old machine at once; you may need some bootstrapping phase.