Log in

No account? Create an account
Дуэт Тьюринг-машинок - Valse oubliée — LiveJournal [entries|archive|friends|userinfo]

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]
[ delicious | aruslan's delicious ]

[Links:| Tags Profile Friends FG1 PP gamedev XNA FF Entries Comments Memories ]

Дуэт Тьюринг-машинок [Aug. 27th, 2008|06:51 pm]
[Tags|, , ]

Не очень понимаю, чем дуэт параллельно работающих машин Тьюринга отличается от одной, если нас интересует ответ от хотя бы одной из них.

Конструктивно, мы можем написать интерпретатор машины Тьюринга на машине Тьюринга.
Мы можем сделать его "параллельным" путём пошаговой интерпретации каждой из двух программ вместе с их состояниями.
И мы можем остановиться, если хотя бы одна из программ остановилась.

Очень хочется помощи зала.
Вот цытато:

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?)

[User Picture]From: aruslan
2009-01-05 10:48 pm (UTC)
Ага, я массово тупил, спасибо :)
И с Новым годом, вот! :))
(Reply) (Parent) (Thread)