0

Is it possible to develop a set of axioms for solving any problem, that are certain to work? Similar to problem solving strategies or proof strategies, though a set of steps that work indefinitely if applied effectively?

And I mean elementary proofs or problems that have already been solved before.

  • 1
    Looking around the world you live in, can you seriously imagine that we have an algorithm to "solve any problem?" – Kevin Carlson Feb 15 '15 at 02:14
  • 2
    Hilbert asked this same question. Godel said, "Nope". (Turing also said "no") – Milo Brandt Feb 15 '15 at 02:14
  • Not every "math problem" has a solution. For example, I could ask "what is the smallest real number that is larger than 1/2" ? But for problems which have solutions, they can be algorithmically worked out. The question "Does the following statement have a proof of no longer than $N$ characters?" is NP, so it can be done eventually but maybe not in your lifetime. – DanielV Feb 15 '15 at 02:15
  • @Meelo at least Hilbert confined himself to arithmetic! – Kevin Carlson Feb 15 '15 at 02:15
  • 1
    That is misleading. We can solve any problem that is solvable (eventually). – DanielV Feb 15 '15 at 02:16
  • Well there are a finite amount of procedures that you follow when proving something or solving something, so can't they be organized and grouped together in a form of axioms or steps? –  Feb 15 '15 at 02:16
  • @abt Yes. The axioms depend on your logic (different people prefer different axioms), and the steps are called "rules of inferences" which have articles wikipedia or elsewhere. – DanielV Feb 15 '15 at 02:17
  • @DanielV Do you mean in the sense of "The set of theorems is recursively enumerable" (for axiomatic systems to which Godel's theorem is applicable anyways)? I feel like that's equally problematic, because we can't a priori know whether a problem is solvable. – Milo Brandt Feb 15 '15 at 02:19
  • 2
    And then Yuri Matiyasevich said "no," solving Hilbert's Tenth Problem. @Meelo – Thomas Andrews Feb 15 '15 at 02:41
  • 1
    Problem solving has, in a sense, been axiomatized. Let $\varphi$ be a mathematical sentence that can be formulated in the language of ZFC. We can start listing proofs by length. If $\varphi$ or $\lnot \varphi$ can be proved in ZFC, then sooner or later it will show up in the list. Granted, ZFC is incomplete, so the procedure will not always work. Also, even if one of $\varphi$ or $\lnot\varphi$ is a theorem, we cannot find a priori bounds on the length of a proof. – André Nicolas Feb 15 '15 at 03:11

1 Answers1

1

A simple-seeming class of problems - Diophantine equations - cannot be solved by an algorithm of any sort.

A Diophantine equation is an equation of the form $P(x_1,x_2,\dots,x_n)=0$, where $P$ is a polynomial with integer coefficients and you are seeking integer solutions. There is no algorithm to determine if such an equation has a solution.

Turns out, you can restrict the question to polynomials of degree $4$ at most, and it is still unsolvable.

This is called Hilbert's Tenth Problem.

Thomas Andrews
  • 177,126