Cтраница 2
Тьюринг и другие первооткрыватели теории вычислимости были первыми, кто доказал, что некоторые корректно определенные математические задачи неразрешимы, т.е. что в принципе не существует алгоритма, способного к решению всех частных случаев таких задач. [16]
Тьюринг вводит абстрактную модель цифровой вычислительной машины и доказывает неразрешимость проблемы остановки и проблемы разрешимости для логики первого порядка. [17]
Тьюринг рассматривает это как последовательность оче. [18]
Тьюринг изобрел конечные машины, которые выполни алгоритмы, представленные таким способом. [19]
Тьюринга, данное в [3], нельзя улучшить без применения новых методов. [20]
Тьюринга для программирования) не оценивалось бы, скажем, функцией с х 2 при достаточно большом с. А такая оценка примитивно рекурсивна, что позволяет сослаться на только что доказанную теорему. [21]
Тьюринга не могут быть бесконечными десятичными выражениями. Но это запрещено для машин Тьюринга. Мы должны дождаться остановки машины ( сопровождаемой звонком колокольчика. До того момента, пока машина не выполнит команды STOP, выходные данные могут изменяться и поэтому не являются достоверными. С другой стороны, после полной остановки машины результат должен быть с необходимостью конечным. [22]
Тьюринга Н на самом деле не существует. Иными словами, не существует универсального алгоритма для решения вопроса об остановке произвольной машины Тьюринга. [23]
Тьюринга не включает ни одной команды STOP или же, наоборот, состоит только из таких команд, то одного здравого смысла достаточно для решения вопроса о ее остановке. Но не существует ни одного алгоритма, который позволял бы решать любую математическую задачу или давал ответ на вопрос об остановке любой машины Тьюринга при любых вводимых в нее числах. [24]
Тьюринга, изложенными во второй главе, согласно которым не существует общего алгоритма для доказательства математических утверждений. И, как следствие, мы доказали теорему Геделя о том, что ни одна система наподобие задуманной Гильбертом не может быть полной в обсуждаемом нами смысле. [25]
Тьюринга), но способны в некоторых, очень специфических случаях, достигать более высокого быстродействия ( в смысле теории сложности, см. с. Для такой блестящей идеи эти выводы представляются довольно неутешительными, но будем помнить о том, что пока мы стоим у самых истоков. [26]
Тьюринга или в ее выходной ленте) сделала бы ее полностью бесполезной; поэтому трудно понять, как настоящие усовершенствования алгоритмов могут получаться таким вот случайным образом. Даже обдуманные усовершенствования труднореализуемы, когда неизвестен их точный смысл. Так традиционно получается в тех нередко возникающих ситуациях, когда необходимо внести изменения или исправления в сложную и небрежно задокументированную программу, чей автор находится вне пределов досягаемости или давно умер. Тогда вместо того, чтобы пытаться разобраться в хитросплетениях разнообразных промежуточных значений и неявных подзадач, на которых базируется эта программа, иной раз бывает проще стереть все и начать заново. [27]
Тьюрингов ским алгоритмом в алфавите Л называют всякий алгоритм Щ следующего вида. Пусть ЯП, отправляясь от этой исходной конфигурации, заканчивает работу. Рассматривается клетка ленты, находящаяся в поле зрения Щ1 в заключительной конфигурации. Если символ, записанный в ней, пуст, то в качестве 3t ( 5) берется пустое слово. В противном случае в качестве 3t () берется слово, записанное в максимальном, не содержащем пустых клеток отрезке ленты, включающем обозреваемую машиной ЯЛ клетку. [28]
Тьюринга просто перемещается слева направо по своей ленте подобно автомату. [29]
Тьюринга показывает, что каждый бесконтекстный язык является ( Т ( п) п5) - распознаваемым. [30]