Машина Зенона
В математиці та інформатиці, Машина Зенона (іноді скорочується до ЗМ, також називають Прискореною машиною Тьюринга) — це гіпотетична комп'ютерна модель, пов'язана з машиною Тьюринга, яка здатна зробити зліченну кількість алгоритмічних кроків за кінцевий час. У більшості моделей обчислень такі машини не розглядаються.
| Машини Тюрінга |
|---|
| Машина |
|
| Варіанти |
|
| Науковці |
Більш строго, машиною Зенона називають таку машину Тьюринга, якій потрібно 2-n одиниць часу для здійснення n-го кроку. Таким чином, перший крок вимагає 0,5 одиниць часу, другий — 0,25, третій — 0,125 і так далі, так що за одиницю часу відбувається нескінченна кількість кроків.
Ідея машини Зенона вперше обговорювалася Германом Вейлем у 1927. Свою назву вона отримала на честь давньогрецького філософа Зенона Елейского. Такі машини відіграють ключову роль в деяких теоріях. Наприклад, теорія точки Омега, розроблена Франком Тіпплером, вірна, тільки якщо машина Зенона може існувати.
Машина Зенона і обчислюваність
Деякі функції, які не можуть бути обчислені на машині Тьюринга, можуть бути обчислені з використанням машини Зенона. Наприклад, на ній може бути вирішена проблема зупинки (що ілюструється наступним псевдокодом):
початок програми
записати 0 в першу комірку на стрічці;
початок циклу
змоделювати черговий крок роботи даної машини Тьюринга на даному вході;
якщо машина Тьюринга зупинилася, то записати 1 в першу комірку на стрічці і перервати цикл;
кінець циклу
кінець програми
Такі обчислення, що виходять за рамки можливостей машини Тьюринга, називаються гіперобчисленнями і є прикладом суперзадачі.
Варто зауважити, що проблема зупинки для самої машини Зенона не може бути вирішена на машині Зенона. (Potgieter, 2006).
Див. також
Посилання
- Potgieter, Petrus H. (31 липня 2006). Zeno machines and hypercomputation. Theoretical Computer Science 358 (1): 23–33. doi:10.1016/j.tcs.2005.11.040.