결정론적 알고리즘: 두 판 사이의 차이

결정론적 알고리즘은 [[상태 기계]]로 엄밀하게 정의할 수 있다. '상태'라는 것은 특정한 시각에 기계가 어떤 동작을 하는지 설명한다. 상태기계는 한 상태에서 다른 상태로 차례대로 넘어가면서 동작한다. 처음 입력값을 넣으면, 기계는 '초기상태' 혹은 '시작상태'가 된다. 만약 기계가 결정론적이면, 초기상태 이후로 현재 상태가 앞으로 어떤 상태가 될지 결정하며 어떤 상태를 거쳐서 동작할지 미리 결정된다. 어떤 기계가 결정론적이라고 해도 완료상태에 도달하지 못하거나 멈추지 않을 수도 있다.<ref>어떤 상태를 거쳐서 어떤 다음 상태에 도달하는지 미리 알 수 있어도, 완료상태에 도달하지 못하거나 멈추지 않는 경우가 있을 수 있기 때문이다.</ref>