0

So for example, we take a Turing machine $M$ with alphabet $\{0,1\}$ and 10 states, where $q_0$ is the initial state and $q_F$ is the accepting state. For a certain algorithm or calculation $M$ is allowed to take $x$ amount of steps, for example $x = 15$. How many steps does $M$ need to take before you reach a point at which you already know it won't accept the given input?

user5368737
  • 217
  • By "it won't accept the given input" do you mean "it won't accept the given input within a total of $x$ steps"? – Eric Wofsey Oct 09 '15 at 17:21
  • @EricWofsey not 100% sure what you mean, but I mean after how many steps do you already know $M$ won't accept the given input. – user5368737 Oct 09 '15 at 17:25
  • In general there is no computable max. – André Nicolas Oct 09 '15 at 17:25
  • @AndreNicolas it's a question given to me, so how should I answer it. What I mean is, if there is no computable max, how do I prove that? – user5368737 Oct 09 '15 at 17:29
  • If there were a computable max, thre would be an algorithm for determining whether the machine accepts. But we know there is no such general algorithm. – André Nicolas Oct 09 '15 at 17:33
  • @user5368737: You said $M$ is only allowed to take $x$ steps. So in the example you gave, for instance, are you asking whether (say) after 12 steps you might be able to tell whether it won't accept within 15 steps? – Eric Wofsey Oct 09 '15 at 17:37
  • @EricWofsey precisely, so what is the maximum amount of steps you need to take before you are able to tell whether it won't accept it in (in this case) 15 steps. – user5368737 Oct 09 '15 at 17:40
  • You're not going to be able to say anything useful in full generality. Are there some additional things you know about $M$? – Eric Wofsey Oct 09 '15 at 17:42
  • Also, this question is not a mathematically precise one unless you define what methods you are allowed to use to "tell whether it won't accept". For instance, presumably you don't want to allow yourself to just do computations from the current state of the machine to mimic running it the rest of the way. – Eric Wofsey Oct 09 '15 at 17:46
  • @EricWofsey the question given to me is "if $M$ has 10 states, where $q_0$ is the initial state and $q_f$ is the accepting state, and $M$ is allowed to take 15 steps to solve a certain calculation/algorithm, what is the maximum amount of steps that $M$ can take before you know if it won't* accept the given input?" – user5368737 Oct 09 '15 at 17:46
  • Well, without more context explaining what the question means, it is impossible to answer. – Eric Wofsey Oct 09 '15 at 17:48
  • @EricWofsey all else it says is the alphabet (${0,1}$) and that the memory that a Turing machine uses in a calculation is the amount of cells that are written on. The memory usage is also a function of the length of the input, and the length of the input is the amount of non-empty cells at the start of the calculation. – user5368737 Oct 09 '15 at 17:52

0 Answers0