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

Question

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

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

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

1

turing-machines turing-complete

Источник

user444869 11 сен '10 в 01:10

4 ответа

Другие вопросы по тегам turing-machines turing-complete

user438039 11 сен '10 в 01:15 2010-09-11 01:15 · Answer 1 · 2010-09-11 01:15

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

5

Источник

user438039 11 сен '10 в 01:15

user443341 11 сен '10 в 01:15 2010-09-11 01:15 · Answer 2 · 2010-09-11 01:15

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

user243712 11 сен '10 в 01:12 2010-09-11 01:12 · Answer 3 · 2010-09-11 01:12

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

1

Источник

user243712 11 сен '10 в 01:12

user363751 11 сен '10 в 05:17 2010-09-11 05:17 · Answer 4 · 2010-09-11 05:17

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