Question

For each of the questions below, write a paragraph using an outside source. Be sure to include a reference of your outside source.

Give a short biography of Alan Turing. In your own words, what is the halting problem?

Answer 1

1.

Alan Turing: Founder of Computer Science
(Reference: Jonathan P. Bowen Division of Computer Science and Informatics School of Engineering London South Bank University
Borough Road, London SE1 0AA, UK Museophile Limited, Oxford, UK)

Alan Mathison Turing was born in London, England, on 23 June 1912. Ed-
ucated at Sherborne School in Dorset, southern England, and at King’s College, Cam-
bridge, he graduated in 1934 with a degree in mathematics. Twenty years later, after a
short but exceptional career, he died on 7 June 1954 in mysterious circumstances. He is
lauded by mathematicians, philosophers, and computer sciences, as well as increasingly
the public in general.
Unlike some theorists, Turing was willing to be involved with practical aspects and
was as happy to wield a soldering iron as he was to wrestle with a mathematical prob-
lem, normally from a unique angle. With hindsight, Turing’s 1936 seminal paper on
computable numbers foretold the capabilities of the modern computer. World War II
(1939–45) then brought about a radical, but perhaps fortuitous, change of direction in
Turing’s career, as his unique mathematical abilities were recognized during his time
at Cambridge and he was invited to join Bletchley Park, the centre of the United King-
dom’s efforts to break German secret codes. Decryption was laborious to do by hand
in the time needed and Turing recognized that machines, together with great human
ingenuity, could tackle the problem far more quickly and reliably.

2.

Halting Problem

In theory of computability , the halting problem is a decision problem which can be stated as follows: Given a explanation of a program , decide whether the program finishes running or continues to run, and will thus run forever. This is corresponding to the problem of deciding, given a program and an input, whether the program will ultimately halt when run with that input, or will run forever. Halting problems played a central role in computability theory right up from the launching.

(Reference: Sadia Ynas Butt, Halting Problem, Jornal of problem solving)

Assume we have fixed some finite descriptions of Turing machines. Using these, explanation
we can enumerate Turing machines via their descriptions, say, ordered by the lexicographic ordering. Each Turing machine thus receives an index : its place in the enumeration M​​​​​​1, M​​​​​​2, M​​​​​​3, . . . of Turing machine descriptions.

Halting function: The halting function h is defined as

(Halting problem). The Halting Problem is the problem of determining (for any e, n) whether the Turing machine M​​​​​​e halts for an input of n .