Алгоритм — це набір інструкцій, що описують порядок дій виконавця для досягнення результату рішення задачі за кінцеве число дій, при будь-якому наборі вихідних даних. У трактуванні старої замість слова «порядок» використовувалося слово «послідовність», але в міру розвитку паралельності в роботі комп'ютерів слово «послідовність» стали замінювати більш загальним словом «порядок». Це пов'язано з тим, що робота якихось інструкцій алгоритму може бути залежна від інших інструкцій або результатів їх роботи. Таким чином, деякі інструкції повинні виконуватися строго після завершення роботи інструкцій, від яких вони залежать. Незалежні інструкції, що стали незалежними через завершення роботи інструкцій, від яких вони залежать, можуть виконуватися в довільному порядку, паралельно або одночасно, якщо це дозволяють використовуються процесор і операційна система.
Раніше часто писали «алгорифм», зараз таке написання використовується рідко, але, тим не менш, має місце (наприклад, Нормальний алгорифм Маркова).
Часто в якості виконавця виступає певний механізм (комп'ютер, токарний верстат, швейна машина), але поняття алгоритму необов'язково відноситься до комп'ютерних програм, так, наприклад, чітко описаний рецепт приготування страви також є алгоритмом, в такому випадку виконавцем є людина.
Поняття алгоритму належить до первісних, основним, базисним поняттям математики. Обчислювальні процеси алгоритмічного характеру (арифметичні дії над цілими числами, знаходження найбільшого спільного дільника двох чисел і т. д.) відомі людству з глибокої давнини. Проте в явному вигляді поняття алгоритму сформувалося лише на початку XX століття.
Часткова формалізація поняття алгоритму почалася зі спроб рішення проблеми дозволу (ньому. Entscheidungsproblem), яку сформулював Давид Гільберт в 1928 році. Наступні етапи формалізації були необхідні для визначення ефективних обчислень[] або «ефективного методу»[]; серед таких формализаций — рекурсивні функції Геделя — Эрбрана — Кліні 1930, 1934 та 1935 років, λ-числення Алонзо Черча 1936 р., «Формулювання 1» Еміля Поста 1936 року і машина Тюрінга. У методології алгоритм є базисним поняттям і одержує якісно нове поняття як оптимальності по мірі наближення до прогнозованого абсолюту. У сучасному світі алгоритм у формалізованому виразі складає основу освіти на прикладах, за подобою.
Основна ідея, що лежить в основі машини Тюрінга, дуже проста. Машина Тьюрінга — це абстрактна машина (автомат), що працює з стрічкою окремих осередків, в яких записані символи. Машина також має головку для запису і читання символів з комірок, яка може рухатися вздовж стрічки. На кожному кроці машина зчитує символ з комірки, на яку вказує головка, і, на основі зчитаного символу і внутрішнього стану, робить наступний крок. При цьому машина може змінити свій стан, записати інший символ в клітинку або пересунути голівку на одну клітинку вправо або вліво.[]
На основі дослідження цих машин був висунутий теза Тюрінга (основна гіпотеза алгоритмів): Певний алгоритм для знаходження значень функції, заданої на деякому алфавіті, існує тоді і тільки тоді, коли функція обчислюється по Тьюрингу, тобто коли її можна обчислити на машині Тьюринга.
Ця теза є аксіомою, постулатом, і не може бути доведений математичними методами, оскільки алгоритм не є точним математичним поняттям.
Різні визначення алгоритму в явній або неявній формі містять наступний ряд загальних вимог: Дискретність — алгоритм повинен представляти процес рішення задачі як послідовне виконання деяких простих кроків. При цьому для виконання кожного кроку алгоритму потрібно кінцевий відрізок часу, тобто перетворення вихідних даних у результат здійснюється дискретно в часі. Детермінованість (визначеність). У кожен момент часу наступний крок роботи однозначно визначається станом системи. Таким чином, алгоритм видає один і той же результат (відповідь) для одних і тих самих вихідних даних. У сучасному трактуванні в різних реалізацій одного й того ж алгоритму повинен бути изоморфный граф. З іншого боку, існують імовірнісні алгоритми, в яких наступний крок роботи залежить від поточного стану системи і генерованого випадкового числа. Однак при включенні методу генерації випадкових чисел в список «вихідних даних» імовірнісний алгоритм стає підвидом звичайного. Зрозумілість — алгоритм повинен включати тільки ті команди, які доступні виконавцю і входять у його систему команд. Завершаемость (кінцівку) — при коректно заданих вихідних даних алгоритм повинен завершувати роботу і видавати результат за кінцеве число кроків.[] З іншого боку, імовірнісний алгоритм може і ніколи не видати результат, але ймовірність цього дорівнює 0. Масовість (універсальність). Алгоритм повинен бути застосовний до різних наборів вихідних даних. Результативність — завершення алгоритму певними результатами. Алгоритм містить помилки, якщо призводить до отримання неправильних результатів або не дає результатів. Алгоритм не містить помилок, якщо він дає правильні результати для будь-яких допустимих вихідних даних.
