1
$\begingroup$

Is there an example of a "set of steps" that we thought was an algorithm, but later was shown not to be an algorithm because it could not be implemented on a Turing machine?

$\endgroup$

2 Answers 2

2
$\begingroup$

The Church–Turing thesis states that every algorithm can be implemented on a Turing machine. It has stood the test of time. In particular, I believe that the answer to your question is negative.

The appearance of quantum algorithms, in particular Shor's factorization algorithm, has called into question the efficient Church–Turing thesis (sometimes known as the Cook–Karp thesis), which states that $\mathsf{P}$ captures the class of efficiently solvable problems; but quantum computers are known to compute the same class of languages as classical computers.

$\endgroup$
2
$\begingroup$

When Hilbert set out his famous list of problems in 1900, the tenth problem was posed as follows:

"Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers"

This wording strongly suggests that Hilbert (and the majority of the mathematical community at that time) believed a "set of steps" existed that could solve any system of Diophantine equations, given enough time and resources. Hilbert's challenge was to "devise" i.e. to formally document this process in a "finite number of operations" - what in modern terms we would call an algorithm.

We now know that Hilbert's tenth problem is undecideable, and the general algorithm that Hilbert was asking for does not exist.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.