В математиці та інформатиці Машина Зенона іноді скорочується до ЗМ також називають Прискореною машиною Тьюринга це гіпот

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

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

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

Машина Зенона і обчислюваність

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

початок програми записати 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.