|
|
|
== 엄밀한 정의 ==
결정론적 알고리즘은 [[상태 기계]]로 엄밀하게 정의할 수 있다. '상태'라는 것은 특정한 시각에 기계가 어떤 동작을 하는지 설명한다. 상태기계는 한 상태에서 다른 상태로 차례대로 넘어가면서 동작한다. 처음 입력값을 넣으면, 기계는 '초기상태' 혹은 '시작상태'가 된다. 만약 기계가 결정론적이면,초기상태 이후로 현재 상태가 앞으로 어떤 상태가 될지 결정하며 어떤 상태를 거쳐서 동작할지 미리 결정된다. 어떤 기계가 결정론적이라고 해도 완료상태에 도달하지 못하거나 멈추지 않을 수도 있다. (어떤 상태를 거쳐서 어떤 다음 상태에 도달하는지 미리 알 수 있어도, 완료상태에 도달하지 못하거나 멈추지 않는 경우가 있을 수 있기 때문이다.)
<!--
Formally, deterministic algorithms can be defined in terms of a [[state machine]]: a ''state'' describes what a machine is doing at a particular instant in time. State machines pass in a discrete manner from one state to another. Just after we enter the input, the machine is in its ''initial state'' or ''start state''. If the machine is deterministic, this means that from this point onwards, its current state determines what its next state will be; its course through the set of states is predetermined. Note that a machine can be deterministic and still never stop or finish, as long as we can predict with certainty what states it will pass through.
결정론적인 성질을 가지는 [[추상기계]]의 예에는 [[결정론적 튜링 기계]]와 [[결정론적 유한 자동장치]]가 있다.
Examples of particular [[abstract machine]]s which are deterministic include the [[deterministic Turing machine]] and [[deterministic finite automaton]].
-->
== 비결정론적 알고리즘 만들기 ==
<!--
|
