Полнота по Тьюрингу

Question

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

Означает ли это, что я теоретически могу реализовать Google с помощью JavaScript или Brainf_ck ?

Answer 1

Вы можете реализовать Google из стековой машины, сделанной из спичечных коробок и камней.Yabba-Dabba-Ду?

Answer 2

Нет, для приведенных примеров это было бы невозможно.Завершение полноты - это реализация алгоритмов и тому подобного, но вам не будет сказано, не можете ли вы внедрить в нее какое-либо программное обеспечение.Google в основном зависит от их баз данных, с которыми вы не можете работать напрямую через JavaScript, поэтому нет DB == нет Google.

Answer 3

Помимо вопросов производительности ввода / вывода, существуют также вопросы времени выполнения.Количество шагов, необходимых для выполнения одной задачи с помощью машины Тьюринга, может быть на сотни порядков больше, чем количество шагов, необходимых для того же действия на другой машине с Тьюринга.Таким образом, вполне возможно, что одна машина сможет за доли секунды выполнить задачу, которая будет держать другую машину занятой до конца вселенной;если бы последней машине каким-то образом было позволено продолжать работать даже после окончания вселенной, она могла бы дать ответ, но с практической точки зрения последняя машина была бы неспособна эффективно решить проблему, несмотря на ее полноту по Тьюрингу.

Answer 4

Да, все, что они могут вычислить, вы можете делать на этих языках.Но это ничего не говорит об объеме памяти или другого необходимого хранилища, о том, как быстро он будет работать, или о простоте записи или отладки.