It would be very nice to have a program to which we could submit new code for a quick determination as
to whether it would run to completion given any particular set of inputs. Alas, Turing proved that this cannot
be. One can and should write test programs, but one will never succeed in writing one program which can test
every program.
The ???halting problem??? is one of the provably unsolvable problems in computing (Turing, Alan, ???On computable
Numbers with an Application to the Entscheidungsproblem???, Proceedings of the London Mathematical
Society, 2:230??“265, 1936). No one algorithm will ever be written to prove the correct or incorrect execution
of every possible program when presented with any particular set of inputs. While no such algorithm can be
successful, knowing that allows computer scientists to focus on problems for which there are solutions.
SUMMARY
An algorithm is a specific procedure for accomplishing some job. Much of computer science has to do with
finding or creating better algorithms for solving computational problems.
We usually describe computational algorithms using pseudocode, and we characterize the performance of
algorithms using the term ???order of growth??? or ???theta.
Pages:
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86