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
