Машина Зенона

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

В математиці та інформатиці, Машина Зенона (іноді скорочується до ЗМ, також називають Прискореною машиною Тьюринга) — це гіпотетична комп'ютерна модель, пов'язана з машиною Тьюринга, яка здатна зробити зліченну кількість алгоритмічних кроків за кінцевий час. У більшості моделей обчислень такі машини не розглядаються.

Більш строго, машиною Зенона називають таку машину Тьюринга, якій потрібно 2-n одиниць часу для здійснення n-го кроку. Таким чином, перший крок вимагає 0,5 одиниць часу, другий — 0,25, третій — 0,125 і так далі, так що за одиницю часу відбувається нескінченна кількість кроків.

Ідея машини Зенона вперше обговорювалася Германом Вейлем у 1927. Свою назву вона отримала на честь давньогрецького філософа Зенона Елейского. Такі машини відіграють ключову роль в деяких теоріях. Наприклад, теорія точки Омега, розроблена Франком Тіпплером[en], вірна, тільки якщо машина Зенона може існувати.

Машина Зенона і обчислюваність[ред.ред. код]

Деякі функції, які не можуть бути обчислені на машині Тьюринга, можуть бути обчислені з використанням машини Зенона. Наприклад, на ній може бути вирішена проблема зупинки (що ілюструється наступним псевдокодом):

початок програми 
  записати 0 в першу комірку на стрічці;
  початок циклу
    змоделювати черговий крок роботи даної машини Тьюринга на даному вході;
    якщо машина Тьюринга зупинилася, то записати 1 в першу комірку на стрічці і перервати цикл;
  кінець циклу
кінець програми

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

Варто зауважити, що проблема зупинки для самої машини Зенона не може бути вирішена на машині Зенона. (Potgieter, 2006).

Див. також[ред.ред. код]

Посилання[ред.ред. код]

  • Potgieter, Petrus H. (31 July 2006). Zeno machines and hypercomputation. Theoretical Computer Science 358 (1). с. 23–33. doi:10.1016/j.tcs.2005.11.040.