0
$\begingroup$

Let we fix $<T>$ and $w$, where $<T>$ is its binary representation of a Turing machine and $w$ is input.

We want to check if $T$ doesn't halt over $w$ before $2^{|w|}$ steps. A trivial solution is to use a universal Turing machine which simulates $T$ on $w$ and counts its steps, but this method uses exponential time.

I wish to know do we have any polynomial time algorithm to check this for the fixed Turing machine and input?

If we had a high-level program or pseudo code, then we had the possibility to analyze it and figure out the time complexity without simulation. But by Rice theorem, we know that it is not possible to understand the behaviour of a Turing machine using its binary representation string. So it seems impossible to have a Turing machine which runs in polynomial time and understand that $T$ doesn't halt less than $2^{|w|}$ steps even for a fixed $T$ and $w$. I don't know how to prove it.

Edit (In order to be more clear about inputs and outputs):

There are two possible ways to think of it:

  • We want a Turing machine $M$ that runs in polynomial time over its empty tape and outputs 0 if $T$ halts over $w$ before $2^{|w|}$ steps and outputs 1 otherwise.

  • We want a Turing machine $M$ that runs in polynomial time over input $<T>w$ and outputs 0 if $T$ halts over $w$ before $2^{|w|}$ steps and outputs 1 otherwise. It's not important for us that what is $M$ output for other inputs.

I believe there is no such $M$ since it is not possible to understand what is a Turing machine doing without simulation of its steps. If such $M$ exists, then it is understanding somehow how $T$ acts on $w$ without simulation of $T$ on $w$. Of course for special cases like pseudo-code, we can estimate the running time. But the $T$ which we fix is not always a pseudo-code.

Edit 2: In order to fix the point Ariel mentioned in his answer,

We want a Turing machine $M$ with the second formulation that works correctly as we stated (it understand T takes exponential time running its input) for two inputs $<T>w_1$ and $<T>w_2$.

$\endgroup$
  • 1
    $\begingroup$ What exactly is the problem? Is T part of the input, or is $T$ fixed and the input consists only of $w$? $\endgroup$ – Ariel Nov 14 '17 at 6:58
  • $\begingroup$ @Ariel Both $T$ and $w$ are fixed. The problem is to find a Turing machine that runs in polynomial time and find out if $T$ does not halt on $w$ before $2^{|w|}$ steps. $\endgroup$ – Doralisa Nov 14 '17 at 7:04
  • $\begingroup$ @Ariel I think there is no such Turing machine which runs in poly time and understands whether $T$ does not halt over $w$ before $2^{|w|}$, because it seems such Turing machine is understanding the behavior of $T$ on $w$ that is not possible without simulation. $\endgroup$ – Doralisa Nov 14 '17 at 7:08
  • 1
    $\begingroup$ You have to formally define your problem, if both $T,w$ are fixed, then there's no input and it is not clear what machine you're looking for. Please specify what inputs you expect to handle, and what is the desired output, e.g. for the halting problem the input is an encoding of a machine and some word (they are not fixed/hardcoded, but are given as input) and we want to know whether the machine halts on the given word. $\endgroup$ – Ariel Nov 14 '17 at 7:08
  • $\begingroup$ "But by Rice theorem, we know that it is not possible to understand the behaviour of a Turing machine using its binary representation string." -- Huh? That's an ... interesting interpretation. $\endgroup$ – Raphael Nov 14 '17 at 9:26
0
$\begingroup$

Your first formulation isn't very useful, as either the machine which simply writes $0$ on its tape (without putting in any effort) or the one which writes $1$, satisfy your condition. Fixing both $T,w$ means you have only one question at hand, and not a computational task we can reason about in terms of the amount of resources require to handle it. In that case, a simple yes or no consists as a valid answer, and we can output it in constant time.

In your second formulation, you're asking whether the language

$L=\{(\langle M \rangle,w)| \text{$M$ halts on $w$ within $2^{|w|} steps$}\}$

is decidable in polynomial time? The answer is no, since $L$ is hard (under polynomial time reductions) for the class $\mathsf{DTIME\left(2^n\right)}$. This means that if $L\in P$ then $\mathsf{P=DTIME\left(2^n\right)}$, contradicting the time hierarchy theorem.

$\endgroup$
  • $\begingroup$ I agree that the first formulation isn't very useful, But I disagree about the second one. I'm completely aware that the $L$ you defined above is an EXP-time complete language. My question was about a RESTRICTED version, which is deciding about finite instances of $L$. For example, suppose T is a TM which check $\phi$ as its input is a tautology by checking all possible assigned values. We as human by reading <T> understand T's work takes exponential time. Does any TM exist that that take <T> and $\phi$ as input and answer Yes T use more than $2^{|\phi|}$ steps? continue on next comment $\endgroup$ – Doralisa Nov 15 '17 at 2:05
  • $\begingroup$ A spoil answer to above question is that there is a $M$ which checks whether the coding <T> we get as input is equal to <T> or not. This method works only for the case which <T> have polynomial relation with $w$. If |<T>| be greater than $2^{|w|}$, it will be useless. Note that maybe my belief about my question's answer be wrong. In the other words, maybe there are infinitely many $M_1, M_2, ...$ that accept each instance of $L$ in polynomial time. $\endgroup$ – Doralisa Nov 15 '17 at 2:17
  • $\begingroup$ You seem to be missing the first point. If you're dealing with only a finite amount of instances, then the problem is trivially in $P$ by hardcoding the correct answers into the machine. "If $|\langle T \rangle |$ is greater than $2^|w|$ it will be useless", why? It seems you are confusing the actual input with your behind the scenes (fixed) machine $T$. Specify the input and output you desire, and you will find that the length of the encoding of $T$ doesn't really matter. $\endgroup$ – Ariel Nov 15 '17 at 6:01
  • $\begingroup$ I understand it now. Just one question more, if we want to check $2^{w}$ different $w$ for $T$ ($2^{|w|}$ instances for all $w$ on $T$) and we restrict that the binary string representation of $M$ be polynomial of $|<T>w|$, is it still possible to hardcode correct answer on the $M$? $\endgroup$ – Doralisa Nov 15 '17 at 13:01
  • $\begingroup$ I cant understand what you're asking. What do you mean by checking $2^{|w|}$ different $w$, who is $w$? I cant parse "$2^{|w|}$ instances for all $w$ on $T$", at the beginning you're using $w$ as a variable, then you're quantifying over it. Who are $M,w,T$? If you're gonna use variable names, you're gonna have to declare them, I can't guess what you mean. For example: "I'm looking for a Turing machine which given input $w$, outputs $1$ iff $T$ halts on $w$, where $T$ is some fixed Turing machine". This is a reasonable statement, all the variables are previously defined or quantified. $\endgroup$ – Ariel Nov 15 '17 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.