Детерминируют

Детерминизм — это философское учение (см. Философия) о закономерной универсальной взаимосвязи и взаимообусловленности явлений объективной действительности (см. Сущее, Мир). Детерминизм, как термин и обобщающее понятие, служит для обозначения класса философских концепций, утверждающих или признающих обусловленность, определяемость (детерминированность) всех существующих явлений наблюдаемого мира, включая и человека с его внутренним, субъективным, духовным миром, и некоторой первичной, субстанциальной реальностью (например, Богом — теологический детерминизм, природой — натуралистический детерминизм, или космосом — космологический детерминизм и другие). Однако чаще с понятием детерминизма связывают философское учение о естественной причинной обусловленности всех явлений объективного мира их универсальной, закономерной взаимосвязи и взаимозависимости.

Философский детерминизм, сформулированный ещё древнегреческими материалистами-атомистами, оформился в классической философии как вид логического определения понятия (см. Понятие), противостоящий генерализации (обобщению). В XVI–XVII веках понятие детерминизма начинает приобретать новый смысл — смысл обусловленности — и употребляется в этике для выражения позиции, противостоящей «свободе воли». В XVII веке в период выработки элементарных понятий механики происходит сближение понятия детерминизма и причинности, устанавливается тесная связь категории закономерности и причинности, закладываются основы механистического детерминизма. Успехи механики закрепляют представления об исключительно динамическом характере закономерностей, об универсальности причинной обусловленности. Причинность становится формой выражения законов науки (см. Наука), содержанием детерминистской формы объяснения явлений. Полное и гармоническое слияние механической причинности и детерминизма происходит в концепции Пьер-Симона Лапласа. Центральной становится идея о том, что всякое состояние Вселенной есть следствие предыдущих и причина последующих её состояний. Сформированное им понятие причинно-следственных цепей, последующее отождествление этого понятия с понятием связи состояний и теоретико-механическим представлением о движении окончательно утверждают универсальный объяснительный статус лапласовского детерминизма. Одновременно с этим процессом в концепции лапласовского детерминизма наметился выход за рамки механистической методологии в силу немеханистического, но статистического, вероятностного характера закономерностей, которые исследовались Лапласом. Он обосновывал эвристическую ценность новых математических вероятностных методов, но в рамках доминирующих в то время механистических идеалов и норм научного исследования.

Философский детерминизм сыграл значительную роль в развитии науки Нового времени, и сам, в свою очередь, проделал сложную эволюцию в своём развитии под влиянием научных достижений и общественной практики. Длительное время детерминизм был частью общих материалистически-механистических представлений о мире и процессе его познания, сложившихся в естествознании XVII–XVIII веков и господствовавших в нём, по существу, до конца XIX века. В рамках этих представлений мир рассматривался как гигантский механизм, все действия которого строго однозначно детерминированы в своём появлении и изменении чисто материальными причинными взаимодействиями и в конечном счёте законами механики Ньютона. Ум, которому было бы доступно знание всех координат и скоростей существующих в мире тел и который был бы способен произвести соответствующие математические вычисления, мог бы точно предсказать будущую судьбу мира (и любого явления в нём), как, впрочем, определить и его прошлое состояние. В таком мире нет места не только какому-либо произволу или провидению, но и случаю, возможности, вероятности (концепция абсолютного или лапласовского детерминизма). Но уже с середины XIX века стали возникать концепции (статистическая физика, теория естественного отбора в биологии и другие), которые выходили за рамки такого представления о мире.

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

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

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

  1. Количественная самодетерминация последующего (состояния системы) предшествующим (состоянием).
  2. Механическая детерминация последующего предшествующим с прибавлением действующих причин и взаимных действий.
  3. Статистическая детерминация конечного результата объединённым действием независимых сущностей.
  4. Структурная (или холистская) детерминация частей целым.
  5. Телеологическая детерминация средств целями или задачами.
  6. Диалектическая детерминация или качественная самодетерминация всего процесса внутренней «борьбой» существенных противоположных сторон, или компонентов, системы.
  7. Взаимодействие, или детерминация следствия взаимным действием двух (или более) сущностей.

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

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

Методологическая природа (см. Методология) принципа детерминизма проявляется в том, что он выступает не только как философское учение, но и конкретно-научный норматив описания и объяснения универсальной закономерной связи и обусловленности развития и функционирования определённым образом системно-организованных объектов в процессе их взаимодействия. Принципиальная историчность этого учения обусловлена необходимостью формирования новых естественнонаучных форм детерминизма при переходе науки к изучению объектов с новыми системно-структурными характеристиками.

В общественных науках детерминизм рассматривает вопросы о движущих силах и закономерностях общественного развития (см. Общество), о воздействии общества и отдельных его подсистем на формирование человеческих индивидов и их деятельность (см. Деятельность). Центральным вопросом детерминизма здесь является вопрос о существовании и действии законов. Признание законов, по существу, означает возможность научного познания природы и общества, возможностей науки (в её «классическом» понимании), научно ориентированной адаптации человека к различным процессам (или управления ими). Отрицание законов стимулировало взгляд на природу и общество как на полностью неуправляемые и непредсказуемые процессы. Применительно к обществу такой взгляд часто возникал из попыток выявить специфику социальных процессов сравнительно с природными, подчеркнуть значение деятельности людей, индивидуального творчества для хода социальной истории. В таком смысле концепция детерминизма противостоит различным фаталистическим и провиденциалистским концепциям, связывающим процессы обусловливания, детерминирования явлений общества и существования человека с деятельностью разного рода эзотерических субстанций (судьбы, фатума, рока и тому подобных).

Сложность вопроса о социальных законах объясняется и тем, что в процессе становления обществознания доминировало стремление формировать представление о законах общества по образцу законов естественнонаучных. Такой подход порождал упрощённые, «механические» образы и схемы закономерных связей общественной жизни. Эта тенденция не преодолена полностью и до настоящего времени, хотя теперь упрощения общественных законов стимулируются не механикой, а преимущественно биологией. Особую методологическую трудность всегда представляла трактовка законов, выводимая из деятельности взаимообусловленных человеческих индивидов. Понимание общественных условий в качестве продуктов деятельности людей создаёт возможности для преодоления этой трудности.

В специальных науках детерминизм и детерминацию нередко понимают как синоним постоянной и строго однозначной связи. Именно в таком смысле говорят о «детерминированных процессах», «детерминированных механизмах», «детерминированных уравнениях» и так далее. Во всех этих случаях имеются в виду процессы, поддающиеся строго однозначному описанию и предсказанию. Наличие же в поведении систем, объектов и механизмов элементов вероятности, неопределённости квалифицируется в таком случае как отсутствие детерминизма, или индетерминизм. Индетерминизм полностью или частично отрицает универсальный характер принципа причинной обусловленности, то есть существование причинно-следственных связей, как и возможность их детерминистского объяснения. Так, в физике индетерминизм опирался на открытые квантовой механикой объективные непричинные типы взаимосвязей в микромире, в биологии он оформился в учении витализма.

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

Определение:

Недетерминированный конечный автомат (НКА) (англ. Nondeterministic finite automaton, NFA) — пятёрка , где — алфавит, — множество состояний автомата, — начальное состояние автомата, — множество допускающих состояний автомата, — функция переходов.Таким образом, единственное отличие НКА от ДКА — существование нескольких переходов по одному символу из одного состояния.

Процесс допуска

НКА допускает слово , если существует путь из начального состояния в какое-то терминальное, такое что буквы, выписанные с переходов на этом пути по порядку, образуют слово .Теперь это опишем более формально.

Определение:

Мгновенное описание (англ. snapshot) — пара , , .

Определим некоторые операции для мгновенных описаний.

Определение:

Говорят, что выводится за один шаг (англ. directly yields) из , если:

  • ;
  • .

Это также записывают так: .

Определение:

Рефлексивно-транзитивное замыкание отношения обозначается как .
И говорят, что выводится за ноль и более шагов (англ. yields) из , если .

Определение:

НКА допускает (англ. accepts) слово , если .

Язык автомата

Определение:

Множество слов, допускаемых автоматом , называется языком НКА .

  • .

В этом случае также говорят, что автомат распознаёт (англ. recognize) язык .

Язык НКА является автоматным языком, так как для любого НКА можно построить эквивалентный ему ДКА, а значит, вычислительная мощность этих двух автоматов совпадает.

Пример

Finite state machine 4.png

Это НКА, который распознает язык из алфавита , где на четвертой с конца позиции стоит 0.

Алгоритм, определяющий допустимость автоматом слова

Постановка задачи

Пусть заданы НКА и слово . Требуется определить, допускает ли НКА данное слово.

Алгоритм

Определим множество всех достижимых состояний из стартового по слову : .

Заметим, что если , то слово допускается, так как по определению . Таким образом, алгоритм состоит в том, чтобы построить .

Очевидно, что . Пусть мы построили , построим , где . Заметим, что , так как

, .

Теперь, когда мы научились по строить , возьмем и будем последовательно вычислять для .

Таким образом, мы получим , и всё, что осталось — проверить, есть ли в нём терминальное состояние.

Псевдокод

bool accepts(: Automaton, : String): for i = 1 to .length for ( in ) return 

Время работы алгоритма: .

См. также

  • Детерминированные конечные автоматы
  • Построение по НКА эквивалентного ДКА, алгоритм Томпсона

Источники информации

  • Ю. Громкович Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию: Пер. с нем. — СПб.:БХВ-Петербург, 2010. — С. 87. — ISBN 978-5-9775-0406-5
  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman Introduction to Automata Theory, Languages, and Computation. Second edition. P. 71. ISBN 0-201-02988-X
  • Wikipedia — Nondeterministic finite automaton