Are all languages in P?

Problem Detail: 

Are all languages in $\mathbf{P}$?

Note: The definitions of all the symbols and functions here follow the document [1].

The following is my attempt to answer the question. Assume that we design a special Turing machine $M_1$, no matter what the input is, $M_1$ will jump to the state $q_{\rm accept}$ (the accepting state). Because no matter what the input $w$ is, $M_1$ only needs one step to finish the calculation, $T_{M_1}(n) = 1\ \forall n \in \mathbb{N}$. Let $k=1$, then $T_{M_1}(n) \leq n^1 + 1 = n + 1$. Therefore, $M_1$ runs in polynomial time. Then, all languages $L$ are in $\mathbf{P}$.

Reference

[1] S. Cook, The P versus NP problem, [Online] http://www.claymath.org/sites/default/files/pvsnp.pdf.

Asked By : Wei-Cheng Liu

Answered By : Martin Glauer

You are misunderstanding how accepting a language works. A language $L$ is in P iff there is a deterministic Turing Machine that decides whether a word $w$ belongs to $L$ in polynomial time. Deciding means that it return a positive answer iff $w \in L$ and a negative otherwise.

Your approach will return a positive answer in every case. Thus your TM will accept the language $\Sigma^*$ where $\Sigma$ is the input alphabet of your TM.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/57518