Дуэт Тьюринг-машинок
Aug. 27th, 2008 18:51![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
aruslanНе очень понимаю, чем дуэт параллельно работающих машин Тьюринга отличается от одной, если нас интересует ответ от хотя бы одной из них.
Конструктивно, мы можем написать интерпретатор машины Тьюринга на машине Тьюринга.
Мы можем сделать его "параллельным" путём пошаговой интерпретации каждой из двух программ вместе с их состояниями.
И мы можем остановиться, если хотя бы одна из программ остановилась.
Очень хочется помощи зала.
Вот цытато:
Now, since f(k) is determined by a parallel duo of Turing machines that is not, itself, a Turing machine, but which can be viewed as a deterministic Turing oracle, it follows that there is no algorithmic method of determining f(k); in other words, although the number-theoretic function f(x) is a well-defined mathematical concept, f is not a mathematical object. Hence f(x) may be considered as determinate, but uncomputable; its values are essentially unpredictable, and so, by definition, truly random.
(Is the Halting probability a Dedekind real number?)
Конструктивно, мы можем написать интерпретатор машины Тьюринга на машине Тьюринга.
Мы можем сделать его "параллельным" путём пошаговой интерпретации каждой из двух программ вместе с их состояниями.
И мы можем остановиться, если хотя бы одна из программ остановилась.
Очень хочется помощи зала.
Вот цытато:
Now, since f(k) is determined by a parallel duo of Turing machines that is not, itself, a Turing machine, but which can be viewed as a deterministic Turing oracle, it follows that there is no algorithmic method of determining f(k); in other words, although the number-theoretic function f(x) is a well-defined mathematical concept, f is not a mathematical object. Hence f(x) may be considered as determinate, but uncomputable; its values are essentially unpredictable, and so, by definition, truly random.
(Is the Halting probability a Dedekind real number?)
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: Aug. 28th, 2008 08:45 (UTC)а) CCM тезис, если функция вычислима, то f - математический объект, формула (E!y) f(x) = y, PA- доказуема, и наоброт.
б) исходя из (а) доказываем разрешимость задачи останова.
в) берем множество программу длины k, исходя из (б), находим некоторое количество завершившихся - f(k) и получаем вероятность завершения (HP u,k )для определенной длины k или для всех длин i <= k (HP u, i<=k).
г) хотим доказать, сходимость последовательности вероятностей к некоторому вещественному числу, и обламываемся потому что f(k) не является математическим объектом. то есть смысле в чем, что у нас была PA-доказуемая функция, мы взяли три параллельные машины тьюринга, и решили проблему останова. Далее исходя из этого результата мы построили функцию вероятности (HP i<=k), которая уже перестала быть PA-доказуемой(и мат объектом) и соответственно мы не можем доказать сходимость последовательности ее значений.
no subject
Date: Jan. 5th, 2009 22:48 (UTC)И с Новым годом, вот! :))