Детермінований алгоритм

Детерміновані алгоритми можуть бути визначені в терміні кінцевого автомата: стан описує те, що машина робить в конкретний момент часу. Автомати проходять дискретним способом з одного стану в інший. Тільки після того, як ми вносимо вхідні дані, машина знаходиться в первинному або початковому стані. Якщо машина є детермінованою, це означає, що з цього моменту його поточний стан визначає яким буде наступний стан; його курс через безліч станів визначено. Зауважте, що машина може бути детермінованою і може ніколи не зупинитися чи закінчити якусь дію і, відповідно, не спромогтися надати результат обчислень.

Щодо прикладів конкретних абстрактних машин, які є детермінованими, можна віднести детерміновані машини Тьюринга і детермінований скінченний автомат.

Різні фактори можуть змінювати поведінку алгоритму, роблячи її недермінованою:

• Якщо він використовує зовнішні стани, окрім вхідних даних, таких як введення даних користувачем, глобальна змінна, апаратний таймер значення, випадкове значення, або дані, збережені на жорсткому диску.
• Якщо він діє таким чином, що, наприклад, якщо він має кілька процесорів, які записують одні й ті ж самі дані у один і той самий час. В даному випадку, точний порядок, в якому кожен процесор записує дані будуть впливати на результат.
• Якщо апаратна помилка приводить до зміни стану.

Хоча реальні програми рідко є повністю детермінованими, тому що це простіше для людей. З цієї причини, більшість мов програмування і особливо мови функціонального програмування доклали зусиль, щоб запобігти вище описаним подіям, за винятком подій, на контрольованих умовах.

Поширеність багатоядерних процесорів привела до сплеску інтересу до детермінізму в паралельному програмуванні та виклики недетермінованости були добре задокументовані. Цілий ряд інструментів, щоб допомогти впоратися з проблемами, були запропоновані для боротьби з тупиками і умовами гонки.

Недетермінована поведінка програми є вигідна в деяких випадках. Поведінка програми карти перетасовки, використовуваної в грі в блекджек, наприклад, не повинні бути передбачуваними гравцями - навіть якщо вихідний код програми видно. Використання генератора псевдовипадкових чисел часто буває недостатньо для того, щоб гравці не в змозі передбачити результат перетасовки. Розумний гравець може вгадати точно число, генератор буде вибирати і таким чином визначити весь вміст колоди завчасно, дозволяючи йому обдурити; наприклад, групи безпеки програмного забезпечення в надійних Software Technologies був в змозі зробити це для реалізації Texas Hold 'Em Poker, який поширюється ASF Software, Inc, що дозволяє їм послідовно передбачити результат руки завчасно. Ці проблеми можна уникнути, зокрема, за рахунок використання криптографічного безпечного генератора псевдовипадкових чисел, але він як і раніше необхідний для непередбачування випадкового числа, використованого для ініціалізації генератора. Для цієї цілі необхідне джерело недетермінізма, таке, яке є згенероване за допомогою апаратного генератора випадкових чисел.

Зверніть увагу, що негативна відповідь на проблеми P = NP не означатиме, що програми з недетермініроваим виходом теоретично більш потужні, ніж з детермінованим . Складність класу NP  може бути визначена без посилання на недетермінізма, використовуючи визначення верифікатор основі.