logoalt Hacker News

eru • today at 3:52 AM • 1 reply • view on HN

Almost no one uses Turing machines for complexity theory.

At most you use them for stuff like P vs NP, because Turing machines are 'only' polynomially slower than register machines, so it doesn't matter.

But when you are talking about linear vs quadratic on something resembling real computers, Turing machines are the wrong model.


Replies

cubefox • today at 7:32 AM

So what? Using something that can carry out "exact complex arithmetic" is even more wrong.

➕ show 1 reply