![]() Because we only use additional tape cells for writing down the current divisor, and all divisors of sufficiently large values of n! are smaller than n!, the total number of tape cells in play (including input) is certainly less than 2*|input|. #aa#aa# of the tape and looking at a blankĪ simple analysis of the way this TM works shows that the number of additional tape cells used cannot be more than the number of tape cells used by the input. => ^ => ^ => halt-accept since we are at the end Here's an example of how this TM functions: Input: #aaaaaa#aaaaaa#xaaaaa#xaaaaa#
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. Archives
February 2023
Categories |