Вопросы с тегом «church-turing-thesis»

29
Тезис Черч-Тьюринга и вычислительная мощь нейронных сетей

Тезис Черча-Тьюринга утверждает, что все, что может быть вычислено физически, может быть вычислено на машине Тьюринга. В статье «Аналоговые вычисления через нейронные сети» (Siegelmannn and Sontag, теоретическая информатика , 131: 331–360, 1994; PDF ) утверждается, что нейронная сеть определенной...

23
Используют ли какие-либо языки программирования общие рекурсивные функции в качестве основы?

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

15
Машина Тьюринга + замедление времени = решить проблему остановки?

Существуют релятивистские пространства-времени (например, пространства-времени МГ; см. Хогарт, 1994), где мировая линия бесконечной длительности может содержаться в прошлом конечного наблюдателя. Это означает, что обычный наблюдатель может иметь доступ к бесконечному количеству вычислительных...

12
Может ли каждый самоизменяющийся алгоритм моделироваться несамодифицирующимся алгоритмом?

Если у нас есть какая-либо произвольная компьютерная программа, которая может изменить ее инструкции, возможно ли смоделировать эту программу с помощью программы, которая не может изменить ее инструкции? Редактировать: Я новичок в stackexchange, поэтому не уверен, что мне разрешено задавать НОВЫЙ...

10
Ясное, полное, доказательство того, что язык - это язык Тьюринга Конкурирует?

Я видел веб-сайты, которые якобы «доказывают», что HTML5 + CSS является Turing Complete. Я видел сайты, которые якобы «доказывают», что SQL завершен по Тьюрингу. Я видел множество веб-сайтов, которые якобы «объясняют», что значит быть завершенным по Тьюрингу. Достаточно! Где я могу найти книгу...

9
Аналоговые компьютеры и тезис Черча-Тьюринга

Я хотел бы привести цитату из Nielsen & Chuang, Quantum Computing and Quantum Information, издание, посвященное 10-й годовщине, стр. 5 (выделено мной): Один класс вызовов для сильного тезиса Черча-Тьюринга исходит из области аналоговых вычислений. За годы, прошедшие после Тьюринга, многие...