alt Hacker NewsDid not realize that the model of computation for all of the banner computational complexity results from last week was "exact complex arithmetic." Is this and/or "exact real arithmetic" a common premise for papers in this field? My assumption as an outsider was that people mostly care about things equivalent to Turing machines.
edit: by "things equivalent to" I really mean universal register machines, something that operates on integers and not directly on real numbers.
Replies
No, it’s unusual to use Turing machines as the model.
This kind of this is pretty common (see, for example https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smal...).
There is, of course, the very rich field of Numerical Analysis which deals with how we actually represent these things in real life, but for a starting point assuming this sort of thing is par for the course.
Turing machines are good for computability but not great for complexity.
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.