Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Теорема К. Геделя о неполноте арифметики. Ее философское и методологическое значение в контексте исследований по кибернетике и информатике.

Читайте также:
  1. Esse est percipi» как мировоззренческий ориентир и программа исследований. Субъект как внепространственная и вневременная опора мира
  2. IV-й крестовый поход. Значение крестовых походов
  3. Q – истинное значение измеряемой величины
  4. SADT. Виды, назначение, использование обратной связи на диаграммах.
  5. XIII. ДАННЫЕ ЛАБОРАТОРНЫХ И ИНСТРУМЕНТАЛЬНЫХ ИССЛЕДОВАНИЙ
  6. А)Определители 2-го,3-го и п-го порядков (определения и из св-ва). б)Теорема Лапласа о разложении определителя по элементам строки или столбца.
  7. Автотрофное питание. Фотосинтез, его значение.
  8. Альтернативные правила принятия коллективных решений. Теорема Эрроу о невозможности.
  9. Амнистия и помилование и их уголовно-правовое значение.
  10. Амортизация основных фондов предприятий РГБ: понятие, назначение и методы расчета. Место амортизации в системе формирования инвестиционных ресурсов.

 

Результаты Курта Гёделя в свете проблем информатики: он доказал 2 теоремы, которые разрушили программу финитизма в основании математики, пропагандируемую Гильбертом. Сие есть одно из самых фундаментальных открытий науки 20-го столетия. Некоторые авторы - результаты свидетельствуют о невозможности ИИ, и об ограниченности формальных методов науки.

Теоремы Гёделя:

Первая теорема Гёделя о неполноте

Во всякой достаточно богатой непротиворечивой теории первого порядка (в частности, во всякой непротиворечивой теории, включающей формальную арифметику), существует такая замкнутая формула F, что ни F, ни!F не являются выводимыми в этой теории.

Иначе говоря, в любой достаточно сложной непротиворечивой теории существует утверждение, которое средствами самой теории невозможно ни доказать, ни опровергнуть. Например, такое утверждение можно добавить к системе аксиом, оставив её непротиворечивой. При этом, для новой теории (с увеличенным количеством аксиом) также будет существовать недоказуемое и неопровержимое утверждение.

Вторая теорема Гёделя о неполноте

Во всякой достаточно богатой непротиворечивой теории первого порядка (в частности, во всякой непротиворечивой теории, включающей формальную арифметику), формула, утверждающая непротиворечивость этой теории, не является выводимой в ней.

Иными словами, непротиворечивость достаточно богатой теории не может быть доказана средствами этой теории. Однако вполне может оказаться, что непротиворечивость одной конкретной теории может быть установлена средствами другой, более мощной формальной теории. Но тогда встаёт вопрос о непротиворечивости этой второй теории, и т.д.

Караваев — теорему Гёделя трактуют как результат, ограничивающий возможости человеческого познания вообще, но это не так — теорема Гёделя свидетельствует об открытости мира для нашего познания — если мы возьмём недоказуемую формулу и прибавим её к набору аксиом, получим новую теорию.

Цилищев — математик никогда не имеет дела в своей реальной работе с бесконечным количеством утверждений, поэтому беспокоиться о противоречивости некоторой системы в общем-то не требуется. Ему не надо думать о том, что где-то на бесконечном наборе высказываний ему может встретиться противоречие, ему надо, чтобы тот фрагмент знания, с которым он работает, был непротиворечив. Так же и компьютер — он не будет порождать бесконечное.

Каждая формализация сама порождает прецедент, входящий в идеальное множество, но не подходящий под нее саму. Более того, таким свойством обладает и каждая вычислимая последовательность формализаций. Любая непротиворечивая теория сама помогает построить пример неразрешимого в ней истинного утверждения. (c) Непейвода


 

5. Понятие вычислимости. Разнообразие подходов к уточнению понятия «алгоритм», их предпосылки. Философско-методологические выводы из трудов А. Черча, А. Тьюринга, А. Маркова.

 

Алгоритмы, потенциальная осуществимость, вычислимость

По мнению Д.Кнута, интеллектуальное ядро информатики составляют алгоритмы, а вопрос о том, что алгоритмизируемо, он называет одним из самых волнующих вопросов современности. Понятие алгоритма было известно человечеству давно, однако активные исследования в этой области начали осуществляться с двадцатых годов XX века.

Понятие алгоритма тесно связано с идеализацией (абстракцией) потенциальной осуществимости.
Пример — число (1): 10^10^10

Число большое, но его можно считать конструктивно. Его конструктивность в потенциальной осуществимости процесса его записи — если бы у нас было время и много бумаги, мы могли бы завершить запись этого числа. Для завершения этого процесса, нужно выполнить принципиально конечное число актов поведения. Эти акты поведения могут относиться как к материальным об'ектам, так и к ментальным сущностям. Во избежание всяческих недоразумений, эти действия должны носить элементарный характер. Различный набор элементарных действий определяет различные подходы к уточнению идей вычислимости

1. Рекурсивный подход Чёрча

Основания заложены К.Гёделем. Большое значение в формировании подхода сыграли труды А. Чёрча, Ст. Клини.

Исходные об'екты — натуральные числа. Над ними определяют простейшие функции, именуемые рекурсивными. Примитивно-рекурсивные функции составляют основу математической деятельности (пример — операция взятия числа, следующего за данным).
На основе примитивно-рекурсивных функций строятся более сложные функции.

В некоторых схемах приходится привлекать условный оператор, что вносит некоторого рода неопределенность, которая не принимается в классической теории функций. Однако, такая неопределенность кажется вполне естественной, если смотреть на математику как на творческий процесс, как на процесс создания новых знаковых моделей.

Главное, что все действия являются надежными, т.е. понятными, элементарными и обозримыми.

2. Подход Тьюринга

Он исходил из посылки, что механические операции являются наиболее простыми и надежными. А. Тьюринг предложил принципиально осуществимую конструкцию, которая получила название машины Тьюринга.

Основное свойство машины в том, что она имеет конечное число внутренних состояний. Кроме того, она реагирует на знаки из некоторого набора — внешнего алфавита. Эти знаки нанесены на ленте, которая по предположению является потенциально бесконечной в обе стороны (потому машину и называют абстрактной).

В лице Тьюринга математика вернулась к своему первоисточнику — к механическим материальным процессам. (с) Белков и Тростников

Доказано, что машина Тьюринга в состоянии делать все, что могут делать с числами рекурсивные функции.

3. Подход А.А.Маркова

К каким элементарным и математически точно определенным операциям можно было бы свести все процедуры, широко применяемые в математике и других науках? Искомое точное определение алгоритмов должно соответствовать содержательно-интуитивному пониманию алгоритмов в математике.

В работах Маркова получила развитие идея, что все математические алгоритмы сводятся к повторению одной элементарной операции, выполняемой в строгом соответствии с начертанным на бумаге предписанием, которое после очень простого об'яснения на естественном языке или после демонстрации нескольких примеров, становится ясным каждому человеку, и всеми людьми понимается одинаково.

Алгоритмы по Маркову — это вертикальный список команд (формул подстановки).

Сравнение подходов

аппарат рекурсивных функций ближе всего к классической математике, т.к. оперирует только числами

машины Тьюринга стоят дальше от тех понятий, которые, по традиционному мнению, должны интересовать математика. Но сама идея механистичности имеет давнюю традицию.

алгоритмы Маркова, на первый взгляд представляющие собой "игру в слова", позволяют дать представление о том, что такое алгоритм вообще, и тем самым расширить круг рассматриваемых математиками и информатиками структур и процессов.

Возникает серьезный вопрос — насколько полно рекурсивные функции, машины Тьюринга, алгоритмы Маркова представляют идею вычислимости? Все ли функции могут быть сведены к представленным простейшим операциям? На этот вопрос отвечают тезис Чёрча-Тьюринга (в самой общей форме он гласит, что любая интуитивно вычислимая функция является частично вычислимой, или, что тоже самое, может быть вычислена некоторой машиной Тьюринга) и принцип нормализации Маркова (принцип нормализации эквивалентен тезису Чёрча).

Эти утверждения в принципе недоказуемы, т.к. в них устанавливается тождество между понятиями интуитивными и понятиями строго определенными.

 

Основные понятия и принципы кибернетики. Оформление философско-методологической базы кибернетики в трудах Н. Винера, Р. Эшби, С. Бира.

 

Норберт Винер ввёл термин «кибернетика» в научный лексикон. И. Г. Поспелов отмечает, что приходится признать, что как область знаний кибернетика так и не сложилась. Стаффорд Бир: некоторые считают, что кибернетика является синонимом автоматики, другие — что это опыты с крысами, третьи — область математики, четвёртые — что целью является создание машины, способной управлять целой страной. Стаффорд Бир: основные понятия: понятие системы, управления, обратной связи, модели, алгоритма, чёрного ящика.

Система — любой комплекс динамически связанных элементов. Бир отказался вводить классификацию по признакам (живая/неживая). Но ввел боллее хитрую классификацию:

Степень сложности:

Простые динамические системы

Сложные системы, поддающиеся описанию.

Очень сложные системы.

Природа связей:

Детерминированные

Вероятностные

Каждая система характеризуется по этим двум критериям:

Простая детерминированная система (например, 2 биллиардных шара), чаще всего есть результат сильной абстракции

Сложная детерминированная система (ЭВМ)

Простая вероятностная: подбрасывание монеты

Сложная вероятностная: условные рефлексы животных, механизм прибыльности предприятия

Очень сложные вероятностные системы: экономика государства, человеческий мозг.

Очень сложных детерминированных систем не бывает.

Как различить сложные и очень сложные системы?

Важнейшим признаком является свойственная системе система управления. Сложные вероятностные системы должна исследовать теория операций, а кибернетика должна исследовать очень сложные вероятностностные системы, которые помимо сложности характеризуются гомеостатической природой, т.е. управление осуществляется по принципу обратной связи.

Особый системный подход к объекту исследования.
Существует два подхода: теоретико-множественный и системный.

Теоритические - множества Системный
первичность элемента (и онтологически и гносеологически) первичность целого - система предшествует компонентам
неразборчивость (можно объединять произвольные эл-ты в множества) естественная система: совокупность есть масса элементов общей природы, элементы класса существуют в системе как в целом
априорная индивидуализация абстракция отождествления - элементы должны искусственно выделяться из аморфного поля
внешняя организация: Шрейдер: Организация элементов в множества является внешней по отношению к множеству элементов, т.е. нужен кто-то, кто помыслил бы это множество. внутренняя организация:Представление системы в виде набора подсистем определяется не произволом наблюдателя, а внутренними свойствами самой системы, т.е. сущностью системы по Аристотелю.
теоретико-множественный подход учит видеть во многих повторяющихся явлениях элементы вероятностной природы каждый объект может быть классифицирован на основе сущности системы

Целостность системы доступна непосредственному наблюдению, как некая пространственно-временная организация. Внешние системы — такие системы, чья целостность недоступна непосредственному наблюдению, например, некая экологическая ниша.

Основная цель теории систем - сформировать такую теорию, которая была бы применима к любой системе, независимо от ее природы. На текущем этапе значительных успехов нет.
Саймон: вряд ли можно ожидать от систем столь различного рода (биологических, физических, социальных) существования каких-то общих свойств, которые не являются тривиальными. Зато возникает проблема разработки математического аппарата для исследования систем с точки зрения их целостности. Сам подход оказывается достаточно полезным в некоторых областях знания.

Понятие сложности

Сложность - слово перегружено. Употребляется непонятно и не всегда по делу.

Платон:
Простое — вечное, неизменное, божественное и единое. Душа проста. Сложное — изменчивое, непостоянное, вторичное по природе.

Аристотель: неправильно отождествлять единое и простое. Единое означает меру, а простое — то, что у самой вещи есть определённая природа. Деление: простое — необходимое, а сложное — составное, когда оно мыслится в модусе бытия и разделённое, когда оно мыслится в модусе небытия. Если что-то можно мыслить так или иначе, значит оно является случайным. Т.е. сложное связано со случайностью.

Кузанский: простота — свойство Бога, свойство единого, свойство сущности вещи, необходимое бытие, слияние противоположностей. Сложное — множественность, конечность, случайность. Онтологически простота предшествует сложности, простое постигается непосредственно, при помощи деятельности ума, а сложное — чувственным восприятием, при условии познания простого.

Декарт рассматривает сложное и простое в гносеологическом аспекте, простое — непосредственно, сложное — познанное опосредованно. Гегель — так же. В ХХ столетии учёные исследовали составные объекты.

Саймон: под сложной системой мы понимаем систему, состоящую из большого числа частей, взаимодействующих между собой сложным образом. Какие части считать элементарными — произвол. Главное свойство сложных систем — они проявляются в форме иерархии. Саймон связывает понятие сложности с понятием эволюции и времени.

Р. Карп — сложность может означать много разных вещей: существует дескриптивная сложность и вычислительная сложность. Алгоритм может быть сложен для постороения, но вычисляться быстро.

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

Шрейдер — сложная система — система, которая имеет семиотическую полноценно-языковую природу связи между подсистемами, в противовес простым системам, где имеется только функциональная сигнализация. Т.е. система является сложной, когда она функционирует на основе единой системы ценностей, связывающей её элементы.

—-
Просто на всякий случай - еще одно определение кибернетики + обратной связи
Кибернетика - наука об общих закономерностях процессов управления и передачи информации
Обратная связь — процесс, приводящий к тому, что результат функционирования какой-либо системы влияет на параметры, от которых зависит функционирование этой системы


 




Дата добавления: 2015-02-16; просмотров: 39 | Поможем написать вашу работу | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2024 год. (0.01 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав