First of all, we’re going to create a string by asking this question: A NDTM, trying to solve an undecidable problem, will run k steps? Making a trivial simulation, the machine will run k steps. The answer to the problem is yes.

Second, we’ll take a part of the string generated by the machine (let’s say that the whole string is ‹M_{ND}› and the fragment is ‹M_{ND}‘›) and ask this question to a DTM: Is this string ‹M_{ND}‘›, generated by a NDTM?

About this problem we can say:

– The problem is not only undecidable, is unsolvable… for obvious reasons (like, running until the end of time, a DTM will not find the algorithm which generated the string because is a non-deterministic algorithm). So, it cannot be solved, not only in polynomial time, but it cannot be solved at all. That is: the problem is not in P.

– The same problem can be solved by a NDTM, in polynomial time, because there is a non-deterministic algorithm which will write ‹M_{ND}› just by choosing, every time it writes down, the right symbol of the answer. At the same time, giving to a DTM the string ‹M_{ND}‘› and the string ‹M_{ND}› itself, it can easily (meaning in polynomial time) verify that ‹M_{ND}‘› is a part of ‹M_{ND}›. That is: the problem is in NP.

Third, this being a problem in NP but not in P, we’ll say that P is not equal to NP, and we’ll say that P is a strict subset of NP.

For the beauty of it all, I’ll reformulate the problem: Is ‹this› random? With the (flawed) note: a string generated by a NDTM trying to solve an undecidable problem is true randomness.

I think you’re confused. Non-deterministic Turing machines are as computationally expressive as deterministic ones. There is nothing that one can compute that the other cannot.

Please read the response from https://stanmarian.wordpress.com/2010/07/12/the-ultimate-non-deterministic-turing-machine/

There is no such thing as “non-deterministic algorithm”

Holy shit! i didn’t understand anything at all!