Тьюринга и алгоритмически неразрешимые проблемы
in Лекции по алгебре
as алгебра, лекции, обучение, уравнения, формулы
Алан Тьюринг высказал предположение (известное как Тезис Чёрча — Тьюринга), что любой алгоритм в интуитивном смысле этого слова может быть представлен эквивалентной машиной Тьюринга. Уточнение представления о вычислимости на основе понятия машины Тьюринга (и других эквивалентных ей понятий) открыло возможности для строгого доказательства алгоритмической неразрешимости различных массовых проблем (то есть проблем о нахождении единого метода решения некоторого класса задач, условия которых могут варьироваться в известных пределах). Простейшим примером алгоритмически неразрешимой массовой проблемы является так называемая проблема применимости алгоритма (называемая также проблемой остановки). Она состоит в следующем: требуется найти общий метод, который позволял бы для произвольной машины Тьюринга (заданной посредством своей программы) и произвольного начального состояния ленты этой машины определить, завершится ли работа машины за конечное число шагов, или же будет продолжаться неограниченно долго.
В течение первого десятилетия истории теории алгоритмов неразрешимые массовые проблемы были обнаружены лишь внутри самой этой теории (сюда относится описанная выше проблема применимости), а также внутри математической логики (проблема выводимости в классическом исчислении предикатов). Поэтому считалось, что теория алгоритмов представляет собой обочину математики, не имеющую значения для таких её классических разделов, как алгебра или анализ. Положение изменилось после того, как А. А. Марков и Э. Л. Пост в 1947 году установили алгоритмическую неразрешимость известной в алгебре проблемы равенства для конечнопорождённых и конечноопределённых полугрупп (т. н. проблемы Туэ). Впоследствии была установлена алгоритмическая неразрешимость и многих других «чисто математических» массовых проблем. Одним из наиболее известных результатов в этой области является доказанная Ю. В. Матиясевичем алгоритмическая неразрешимость десятой проблемы Гильберта.
Шаровой сектор
in Конспекты по геометрии
as доказательство, Конспекты по геометрии, лекции, теорема
- Определение: Шаровым сегментом называется часть шара, отсекаемая от него плоскостью.
- Определение: Шаровым слоем называется часть шара, расположенная между двумя параллельными плоскостями, пересекающими шар.
- Определение: Шаровой сектор получается из шарового сегмента и конуса.
- Если шаровой сегмент меньше полушара, то шаровой сегмент дополняется конусом, у которого вершина в центре шара, а основанием является основание сегмента.
- Если же сегмент больше полушара, то указанный конус из него удаляется.
Усеченный конус
in Конспекты по геометрии
as доказательство, Конспекты по геометрии, лекции, теорема
Определение. Конусом называют тело, которое состоит из круга — основания конуса, точки, не лежащей в плоскости этого круга, — вершины конуса и всех отрезков, соединяющих вершину конуса с точками основания — образующие конуса Плоскость, перпендикулярная оси конуса, отсекает от него меньший конус. Оставшуюся часть называют усеченным конусом. Усеченный конус можно получить и как тело вращения. […]
Усеченная пирамида
in Конспекты по геометрии
as доказательство, Конспекты по геометрии, лекции, теорема
Определение. Пирамидой называется многогранник, который состоит из плоского многоугольника — основания пирамиды, точки, не лежащей в плоскости основания — вершины пирамиды и всех отрезков, соединяющих вершину пирамиды с точками основания. Плоскость, параллельная плоскости основания пирамиды и пересекающая пирамиду, отсекает от нее подобную пирамиду. Другая часть пирамиды представляет собой многогранник, который называют усеченной пирамидой. На рисунке […]
Шар
in Конспекты по геометрии
as доказательство, Конспекты по геометрии, лекции, теорема
Определение: Шаром называется тело, которое состоит из всех точек пространства, находящихся на расстоянии, не большем данного, от данной точки. Эта точка называется центром шара, а данное расстояние называется радиусом шара. Граница шара называется шаровой поверхностью или сферой. Любой отрезок, соединяющий центр шара с точкой шаровой поверхности, называется радиусом. Отрезок, соединяющий две точки шаровой поверхности и […]
Цилиндр
in Конспекты по геометрии
as доказательство, Конспекты по геометрии, лекции, теорема
Определение: Цилиндром называется тело, которое состоит из двух кругов, совмещаемых параллельным переносом, и всех отрезков, соединяющих соответствующие точки этих кругов. Круги называются основаниями цилиндра. а отрезки, соединяющие соответствующие точки окружностей кругов, — образующими цилиндра. Основания цилиндра равны и лежат в параллельных плоскостях. У цилиндра образующие параллельны и равны. Поверхность цилиндра состоит из оснований и боковой […]
Конус
in Конспекты по геометрии
as доказательство, Конспекты по геометрии, лекции, теорема
Определение. Конусом называется тело. которое состоит из круга — основание конуса, точки, не лежащей в плоскости этого круга — вершины конуса, и всех отрезков, соединяющих вершину конуса с точками основания. Отрезки, соединяющие вершину конуса с точками окружности основания, называются образующими конуса. Полная поверхность конуса состоит из основания и боковой поверхности. Конус называется прямым, если прямая […]
Призма
in Конспекты по геометрии
as доказательство, Конспекты по геометрии, лекции, теорема
Определение. Призмой называется многогранник, у которого две грани (основания) лежат в параллельных плоскостях, а все ребра вне этих граней параллельны между собой. Грани призмы, отличные от оснований, называются боковыми гранями, а их ребра называются боковыми ребрами. Все боковые ребра равны между собой как параллельные отрезки, ограниченные двумя параллельными плоскостями. Все боковые грани призмы являются параллелограммами. […]
Прямоугольный параллелепипед
in Конспекты по геометрии
as доказательство, Конспекты по геометрии, лекции, теорема
Определение. Параллелепипед — это четырехугольная призма, все грани которой — параллелограммы. Параллелепипеды, как и призмы, могут быть прямыми и наклонными. Определение. Прямой параллелепипед, основанием которого служит прямоугольник, называют прямоугольным параллелепипедом. У прямоугольного параллелепипеда все грани — прямоугольники. Определение. Длины трёх ребер прямоугольного параллелепипеда, имеющих общий конец, называют его измерениями. Определение. Куб — прямоугольный параллелепипед с […]
Взаимное расположение прямых и плоскостей
in Конспекты по геометрии
as доказательство, Конспекты по геометрии, лекции, теорема
Все виды взаимного расположения прямых и плоскостей можно увидеть на слайде: Теоремы Если прямая, пересекающая плоскость, перпендикулярна двум прямым, лежащим в этой плоскости и проходящим через точку пересечения данной прямой и плоскости, то она перпендикулярна плоскости. Если плоскость перпендикулярна одной из двух параллельных прямых, то она перпендикулярна и другой. Если две прямые перпендикулярны одной и […]