[krastanov]

It affects complexity. Sure, it is fascinating to learn there is a separation between computable and not computable tasks, but there is an important separation among the computable tasks as well. There are "practically computable" tasks (computable with a reasonable complexity) and "computable tasks that are still infeasible in the real universe" (e.g. tasks with exponential complexity). Amusingly, it seems that there are also tasks on the border between between practical and infeasible, that can be practically solved on a quantum computer, but can not be solved in a reasonable time on a classical computer (even one as big as the whole universe).

P.S. There was some abuse of naming conventions and nomenclature above.

P.P.S. While computability is a well proven concept, claims about complexity (i.e. practical vs infeasible "computable" tasks) are frequently only conjectures (although they have some supporting empirical observations).

P.P.P.S. The proper terms to google for as a starting point would be (really, this barely scratches the surface):

- complexity class P: computable tasks that can be efficiently solved by a classical computer

- complexity class BQP: computable tasks that can be efficiently solved by a quantum computer (and includes tasks that are conjectured to not be efficiently solvable by a classical computer)

- complexity class NP-hard: computable tasks that are conjectured to not be solvable by a classical or a quantum computer efficiently (i.e. a medium sized problem would take a computer bigger than the universe to solve)