Тьюринга Полнота в реальном времени

Реальные программы могут решать проблемы, учитывая достаточно времени и пространства. Для каждого экземпляра задачи с известным размером фиксируется верхняя граница объема пространства, которое потребляется.Тьюринга Полнота в реальном времени

Существуют ли проблемы, которые не могут быть решены (т. Е. Функции, которые невозможно вычислить), учитывая «просто» достаточно большую память?

Конкретно, существуют ли функции, которые могут быть вычислены только с помощью машины Тьюринга (которая имеет бесконечную ленту), но не обычной программой?

источник

2015-09-18 user3383312

Q1 Да. Q2 Без памяти есть предел .. – Blindman67

Извините, ваш вопрос трудно понять. Что вы подразумеваете под «Для каждого экземпляра проблемы известного размера»? Например, ваша проблема заключается в «Найти первые 1000 простых чисел». Каков его размер? – alisianoi

По размеру я имел в виду размер ввода. Если проблема, о которой вы упомянули, сформулирована так: «Найти первые n простых чисел?», То размер экземпляра проблемы - это необходимое пространство для хранения ввода: log (n), если вы используете двоичную кодировку. – user3383312

Невозможно, чтобы машина Тьюринга фактически потребляла бесконечное количество ленты во время любого конкретного выполнения, так как она должна останавливаться после конечного числа шагов. Если он не останавливается, то он ничего не «решил». Поскольку машина может работать только с конечным числом шагов, она может перемещать только конечное расстояние от начальной точки в любом направлении и, следовательно, потреблять только конечное количество ленты.

Более конкретно, существуют ли функции, которые могут быть вычислены только машиной Тьюринга (которая имеет бесконечную ленту), но не обычной программой?

Несомненно. Но только в силу требования необоснованного (конечного) количества времени или пространства.

источник

2015-09-18 13:25:40 Kevin

Действительно. Однако возможно ли, что машина потребляет конечное количество ленты, значение которой не может быть связано как функция размера ввода? – user3383312

@ user3383312: f (x) = "Количество ленты, необходимое для решения [некоторой проблемы] размера x." Возможно, вы имели в виду [полиномиальную функцию] (https://en.wikipedia.org/wiki/PSPACE) или [экспоненциальную функцию] (https://en.wikipedia.org/wiki/EXPSPACE)? – Kevin

Я думал о следующей фиктивной ситуации: скажем, есть свойство P натуральных чисел, и предположим, что мы знаем, что существует только k натуральных чисел, которые удовлетворяют P. Однако мы не имеем понятия, какое может быть наибольшее такое число. Машина Тьюринга, создающая набор P-чисел, остановится при генерации k чисел, однако она может потреблять сколь угодно большую (но конечную) ленту. Имеет ли это смысл? – user3383312

Тьюринга Полнота в реальном времени

ответ

Смежные вопросы