Editing Abstract machine (section)

== Classification ==
Abstract machines are typically categorized into two types based on the quantity of operations they can execute simultaneously at any given moment: [[Deterministic algorithm|deterministic abstract machines]] and [[Nondeterministic algorithm|non-deterministic abstract machines]].<ref name=":2" /> A [[Deterministic algorithm|deterministic]] abstract machine is a system in which a particular beginning state or condition always yields the same outputs. There is no randomness or variation in how inputs are transformed into outputs.<ref>{{Cite web |title=What is Deterministic System? - Definition from Techopedia |url=http://www.techopedia.com/definition/602/deterministic-system |access-date=2022-05-30 |website=Techopedia.com |date=29 August 2019 |language=en}}</ref> In contrast, a [[Nondeterministic algorithm|non-deterministic]] abstract machine can provide various outputs for the same input on different executions.<ref name=":2" /> Unlike a deterministic algorithm, which gives the same result for the same input regardless of the number of iterations, a non-deterministic algorithm takes various paths to arrive to different outputs.<ref>{{Cite journal |last=Stearns |first=Richard E. |date=January 2003 |title=Deterministic versus nondeterministic time and lower bound problems |url=http://dx.doi.org/10.1145/602382.602409 |journal=Journal of the ACM |volume=50 |issue=1 |pages=91–95 |doi=10.1145/602382.602409 |s2cid=2194820 |issn=0004-5411}}</ref> Non-deterministic algorithms are helpful for obtaining approximate answers when deriving a precise solution using a deterministic approach is difficult or costly.<ref>{{Cite journal |last1=Armoni |first1=Michal |last2=Gal-Ezer |first2=Judith |date=December 2007 |title=Non-determinism: An abstract concept in computer science studies |url=http://dx.doi.org/10.1080/08993400701442885 |journal=Computer Science Education |volume=17 |issue=4 |pages=243–262 |doi=10.1080/08993400701442885 |bibcode=2007CSEd...17..243A |s2cid=41928460 |issn=0899-3408}}</ref>

[[File:2-state 3-symbol Turing Machine.png|thumb|A run of a [[Turing machine]]]]
[[Turing machine|Turing machines]], for example, are some of the most fundamental abstract machines in computer science.<ref name=":2" /> These machines conduct operations on a [[String (computer science)|tape (a string of symbols)]] of any length. Their instructions provide for both modifying the symbols and changing the symbol that the machine’s pointer is currently at. For example, a rudimentary Turing machine could have a single command, "convert symbol to 1 then move right", and this machine would only produce a string of 1s.<ref>{{Cite journal |last=Gill |first=John |date=December 1977 |title=Computational Complexity of Probabilistic Turing Machines |url=http://epubs.siam.org/doi/10.1137/0206049 |journal=SIAM Journal on Computing |language=en |volume=6 |issue=4 |pages=675–695 |doi=10.1137/0206049 |issn=0097-5397}}</ref> This basic Turing machine is deterministic; however, [[Nondeterministic Turing machine|nondeterministic Turing machines]] that can execute several actions given the same input may also be built.<ref name=":2" />