Hamiltonian Paths in Graphs

In this paper, we explore the connections between graphs and Turing machines. A method to construct Turing machines from a general undirected graph is provided. Determining whether a Hamiltonian cycle exists is now shown to be equivalent to solving the halting problem. We investigate applications of the halting problem to problems in number theory. A modified version of the classical Turing machine is now developed to solve certain classes of computational problems.