Editing Computer program (section)

===Universal Turing machine===
[[File:Universal Turing machine.svg|350px|right]]
In 1936, [[Alan Turing]] introduced the [[Universal Turing machine]], a theoretical device that can model every computation.<ref name="discrete-ch10-p654">{{cite book
  | last = Rosen
  | first = Kenneth H.
  | title = Discrete Mathematics and Its Applications
  | publisher = McGraw-Hill, Inc.
  | year = 1991
  | page = [https://archive.org/details/discretemathemat00rose/page/654 654]
  | isbn = 978-0-07-053744-6
  | url = https://archive.org/details/discretemathemat00rose/page/654
  | quote = Turing machines can model all the computations that can be performed on a computing machine.
  }}</ref>
It is a [[finite-state machine]] that has an infinitely long read/write tape. The machine can move the tape back and forth, changing its contents as it performs an [[algorithm]]. The machine starts in the initial state, goes through a sequence of steps, and halts when it encounters the halt state.<ref name="formal_languages-ch9-p234">{{cite book
  | last = Linz
  | first = Peter
  | title = An Introduction to Formal Languages and Automata
  | publisher = D. C. Heath and Company
  | year = 1990
  | page = 234
  | isbn = 978-0-669-17342-0
}}</ref> All present-day computers are [[Turing complete]].<ref name="formal_languages-ch9-p243">{{cite book
  | last = Linz
  | first = Peter
  | title = An Introduction to Formal Languages and Automata
  | publisher = D. C. Heath and Company
  | year = 1990
  | page = 243
  | isbn = 978-0-669-17342-0
  | quote = [A]ll the common mathematical functions, no matter how complicated, are Turing-computable.
}}</ref>