Hot answers tagged


There is a largest $p\in\Bbb N$ such that $y=x^pu$ for some $u\in A^*$. (This $p$ could of course be $0$.) Then $$x^{p+1}u=xy=yz=x^puz\;,$$ so $xu=uz$. The maximality of $p$ ensures that $x$ is not an initial segment of $u$, so $u$ must be an initial segment of $x$, and therefore $x=uv$ for some $v\in A^*$. Then $ux=xu=uvu$, so $z=vu$, and $y=x^pu=(uv)^pu$.


Your "proof" is nonsense for a host of reasons. Here are three: $\mathbf{P} = \mathbf{NP}$ is a definite mathematical question that does not require the supposition of new axioms. $\mathbf{P}$ and $\mathbf{NP}$ are classes of decision problems (i.e., classes of problems of the form "does this input string meet a given criterion"), so "inverse floor ...


I know it's not necessary (or remotely useful) to respond to questions like this, but here goes anyway... I do not think you understand what P and NP mean. It has nothing to do with taking "a countably infinite number of iterations to produce" the answer. If the phrase "polynomially-sized witness" doesn't mean anything to you, read some intro textbooks. ...


A deterministic Turing Machine is just a machine that does only one instruction for a given input. That does not imply that there will be the same output for every input.

Only top voted, non community-wiki answers of a minimum length are eligible