Интернет магазин китайских планшетных компьютеров



Компьютеры - Машина Зенона

23 января 2011


Оглавление:
1. Машина Зенона
2. Машина Зенона и вычислимость



В математике и информатике, Машина Зенона — это гипотетическая компьютерная модель, связанная с машиной Тьюринга, которая способна совершить счётное количество алгоритмических шагов за конечное время. В большинстве моделей вычислений такие машины не рассматриваются.

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

Идея машины Зенона впервые обсуждалась Германом Вейлем в 1927. Своё название она получила в честь древнегреческого философа Зенона Элейского. Такие машины играют ключевую роль в некоторых теориях. К примеру, теория точки Омега, разработанная Франком Типплером, верна, только если машина Зенона может существовать.



Просмотров: 968


<<< Лямбда-исчисление
Машина Тьюринга >>>