The first question emerged from Alonzo Church and Stephen Kleene's work on Lambda Calculus in the 1930s, and was answered formally by Alan Turing in 1936. Turing proved that any computer with some minimal functionality can simulate any other computer, and hence, except for physical limits like the amount of memory available, all computers are equally powerful. Not all problems, however, can be solved by computing. For some problems, there is no program that a machine based on conventional physics can execute that always finishes and produces the correct answer. In particular, Turing showed that it is impossible to create a program that will always correctly answer questions about interesting properties of the information processes described by arbitrary programs such as will this program run ever finish? and is this program a virus?.
No comments:
Post a Comment