Cтраница 1
Доказательство неразрешимости этих задач требует глубоких математических знаний. Глава Декартовы координаты на плоскости познакомит вас с аналитическим методом решения геометрических задач, когда задача переводится на язык формул. Доказано, что если геометрическая фигура, которую мы хотим построить, может быть выражена формулой, содержащей только рациональные функции и действие извлечения квадратного корня, то тогда этот объект можно построить с помощью циркуля и линейки. [1]
Доказательство неразрешимости ( принадлежащее Эрбрану и Черчу) распадается на две части. В первой части показывается, как по любому чистому диадическому предложению F построить чистое предложение G, содержащее лишь единственный трехместный предикатный символ и являющееся общезначимым в том и только в том случае, если F общезначимо. [2]
Доказательство неразрешимости эквивалентности использует неоднозначность рассматриваемых схем. Вопрос об алгоритмической разрешимости свойства однозначности произвольной конечной схемы также является открытым2), хотя теорема 4.9 и решает его для некоторого важного подкласса. [3]
Представляется доказательство неразрешимости задачи о подмножестве для множеств достижимости в сетях Петри. Первоначальное доказательство Рабина как это сообщалось в [26], было дано для систем векторного сложения. Это доказательство имеется также [116] и представлено здесь в гл. [4]
В большинстве случаев доказательства неразрешимости основываются на диагональном методе, как, например, в следующем важном примере. [5]
Доказательство этого факта близко к доказательству неразрешимости уравнений степени 5 в радикалах ( Руффини - Абель - Галуа): оно выводится из неразрешимости некоторой группы. В отличие от обычной теории Галуа, речь идет здесь не о конечной группе, а о неразрешимой группе Ли. Наука, занимающаяся этими вопросами, называется дифференциальной алгеброй. [6]
Проблема усердного бобра ( ее формулировка и доказательство неразрешимости даны Радо Тибором в Bell System Tecnical Journal, May 1962, с. Тьюринга, вычисляющей функцию р, - причем машины, использующей в качестве символов только В к I. Доказательство неразрешимости этой проблемы опирается на свойства функции р, сформулированные в упр. [7]
Точно так же анализ спецификации S может быть наиболее простым способом доказательства неразрешимости. Пусть известно уже, что программа ( Р, G) частично правильна. [8]
В предшествующих главах мы часто пользовались техникой сведения одной проблемы к другой в качестве средства доказательства неразрешимости. [9]
Наш набросок ( который более или менее следует книге А. И. Мальцева 11965 ]), конечно, не является кратчайшим путем к доказательству неразрешимости проблемы равенства, но зато он одновременно вводит ряд стандартных систем для порождения классов языков. Простейшие из этих систем ( конечные автоматы, контекстно-свободные грамматики) будут детально изучены в следующих главах. [10]
Поскольку из ( а) и ( в) следует утверждение, отмеченное на рис. 237 и 238 знаком (), то в совокупности утверждений задачи 159 содержатся все те утверждения, которые были использованы во II доказательстве неразрешимости предыдущей задачи. [11]
Арган ( Арганд), 1806 ], доказательство неразрешимости в радикалах общего алгебраич. Коши основ теории функций комплексного переменного, его работы по строгому обоснованию анализа бесконечно малых, создание II. [12]
Руффини ( 1799 и позднее), посвященных доказательству неразрешимости уравнения 5 - й степени в радикалах, систематически используется замкнутость множества подстановок относительно их умножения и, по существу, описаны подгруппы всех подстановок пятя символов. [13]
В § 1 дается обзор неразрешимых проблем, возникающих в самой теории вычислимости, и обсуждаются некоторые методы доказательства неразрешимости. [14]
Проблема усердного бобра ( ее формулировка и доказательство неразрешимости даны Радо Тибором в Bell System Tecnical Journal, May 1962, с. Тьюринга, вычисляющей функцию р, - причем машины, использующей в качестве символов только В к I. Доказательство неразрешимости этой проблемы опирается на свойства функции р, сформулированные в упр. [15]