Зміст
16 відносини: Квантовий комп'ютер, Пророча машина, Повнота (логіка), Повнота за Тюрингом, Алан Тюрінг, Алонзо Черч, Нормальні алгоритми, Рекурсивні функції, Семантичний розрив, Теза Черча — Тюрінга — Дойча, Універсальні рекурсивні функції, Універсальна машина Тюрінга, Цифрова фізика, Машина Тюрінга, Гіперобчислення, Ефективний метод.
Квантовий комп'ютер
3 кубіти квантового регістра проти 3 бітів звичайного. Квáнтовий комп'ю́тер — фізичний обчислювальний пристрій, функціонування якого ґрунтується на принципах квантової механіки, зокрема, принципі суперпозиції та явищі квантової заплутаності.
Переглянути Теза Черча і Квантовий комп'ютер
Пророча машина
В теорії складності і теорії обчислюваності, пророча машина (oracle machine) — це абстрактний автомат використовний для вивчення проблем вибору.
Переглянути Теза Черча і Пророча машина
Повнота (логіка)
Повнота (або неповнота) у математичній логіці та металогіці — характеристика формальної системи.
Переглянути Теза Черча і Повнота (логіка)
Повнота за Тюрингом
У теорії алгоритмів набір правил маніпуляції даними (набір інструкцій, мова програмування, чи клітинний автомат) вважається повним за Тюрингом тоді і тільки тоді, коли цей набір може моделювати однострічкову машину Тюринга.
Переглянути Теза Черча і Повнота за Тюрингом
Алан Тюрінг
Алан Ма́тісон Тю́рінг (Alan Mathison Turing) (23 червня 1912, Вілмслоу, Чешир, Англія, Велика Британія — 7 червня 1954, Вілмслоу, Чешир, Англія, Велика Британія) — англійський математик, логік і криптограф.
Переглянути Теза Черча і Алан Тюрінг
Алонзо Черч
Алонзо Черч (Алонзо Чорч) (*14 червня 1903, Вашингтон, США — †11 серпня 1995, Гадсон, Огайо, США) — видатний американський математик і логік.
Переглянути Теза Черча і Алонзо Черч
Нормальні алгоритми
Нормальні алгоритми Маркова (нормальна алгорифми) — формалізація поняття алгоритму, що являє собою систему послідовних застосувань підстановок до слів певного алфавіту, введена математиком А.
Переглянути Теза Черча і Нормальні алгоритми
Рекурсивні функції
Рекурсивні функції — клас функцій, введений як уточнення класу обчислюваних функцій.
Переглянути Теза Черча і Рекурсивні функції
Семантичний розрив
Семантичний розрив характеризує різницю між двома описами об'єкту за допомогою різних лінгвістичних репрезентацій (наприклад, мов чи символів).
Переглянути Теза Черча і Семантичний розрив
Теза Черча — Тюрінга — Дойча
Теза Черча — Тюрінга — Дойча, в інформатиці і квантовій фізиці, відома також як CTD-принцип (за абревіатурою від Church, Turing, Deutsch), або як сильна теза Черча — Тюрінга — більш строге у фізичному сенсі формулювання евристичної обчислювальної тези Черча — Тюрінга, запропонована Девідом Дойчем у 1985 році.
Переглянути Теза Черча і Теза Черча — Тюрінга — Дойча
Універсальні рекурсивні функції
У кожній універсальній алгоритмічній системі повинен існувати універсальний алгоритм еквівалентний довільному, наперед заданому алгоритму.
Переглянути Теза Черча і Універсальні рекурсивні функції
Універсальна машина Тюрінга
Універсальна машина Тюрінга Універсальна машина Тюрінга(УМТ) це така машина Тюрінга(МТ) яка може замінити собою будь-яку машину Тюрінга.
Переглянути Теза Черча і Універсальна машина Тюрінга
Цифрова фізика
Цифрова фізика (у фізиці і космології) — сукупність теоретичних поглядів, які випливають з припущення, що Всесвіт описується інформацією, тобто він є обчислюваним.
Переглянути Теза Черча і Цифрова фізика
Машина Тюрінга
Схематична ілюстрація роботи машини Тюрінга. Маши́на Тю́рінга — математичне поняття, введене для формального уточнення інтуїтивного поняття алгоритму.
Переглянути Теза Черча і Машина Тюрінга
Гіперобчислення
Гіперобчисленнями або надтюринговими обчисленнями, (hypercomputation) називають такі обчислення, які не можуть бути виконані на машині Тюрінга.
Переглянути Теза Черча і Гіперобчислення
Ефективний метод
Ефективний методHunter, Geoffrey, Metalogic: An Introduction to the Metatheory of Standard First-Order Logic, University of California Press, 1971 або ефективна процедура у логіці, математиці та інформатиці, особливо у металогіці та теорії обчислюваності - це процедура вирішення проблеми з певного класу.
Переглянути Теза Черча і Ефективний метод
Також відомий як Теорема Черча-Тюринга, Черча теза, Основна гіпотеза теорії алгоритмів.