tions of cryptography upon which today’s electronic
transactions are based. It could give us efficient ways
to solve intractable problems (such as the traveling
salesman problem and the subgraph isomorphism
problem) that arise in mathematics, as well as in every
other science and engineering discipline. A proof in
the negative (P ≠ NP) would have profound theoretical consequences for computer science and mathematics, perhaps by discovering a brand-new proof
technique.
In order to answer what is computable, we must
consider the underlying machine (abstract or physical) that is the computer. Consider the Internet as a
computer. What is a universal machine model for the