One would
not want to write a TM for a complex task like designing a set of stairs for a staircase, but it could be done.
The significance of having such a model of computation is that the model has been used to show that some
tasks cannot be accomplished with a TM. If the Church??“Turing thesis is true, then tasks for which a TM cannot
be successful are tasks which simply have no algorithmic solution.
UNSOLVABLE PROBLEMS
It would be very useful to have a way of quickly knowing whether any particular program, when provided
with any particular set of inputs, will execute to completion and halt, or instead continue endlessly. In computer
science, this is known as the ???halting problem.??? Given a program, and a set of inputs, will the program execute
to completion or not? Is there some algorithm one can apply that will, for any program and any set of inputs,
determine whether the program will run to completion or not?
One might suggest simply running the program, providing the particular inputs, and seeing whether the
program halts or not. If the program were to run to completion and halt, you would know that it halts. However,
if the program were to continue to run, you would never know whether the program would continue forever, or
halt eventually.
Pages:
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83