Question

The theoretical foundation of computer science.

Q. Discuss size trade-offs between Turing machines and programs that compute the same function.

Answer 1

Solution:

Small programs can be executed in O(log n) time or O(n) time which means linearly. This is the running time which we generally get from small programs and this is what is expected from bigger problems as well. It is hard to achieve O(1) running time which is made possible in case of hashing. But there are worst cases too.

But in case of turning machine, it is also same just one need to make sure is that the machine does halt. The key insight is that in order for a Turing machine to halt, it cannot enter a loop. Since a Turing machine will always follow the same sequence after being a specific state, if it ever becomes that same state twice, we know the machine is caught in an infinite loop and will never finish. Therefore, the theoretical maximum number of steps it can run is the maximum number of possible different states for the machine without being the same exact state twice.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)