Открыть сервисСервис

Цик — понятие теории вычислимости

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

Цикл в теории автоматов и алгоритмов

В теории автоматов цикл — это путь в графе состояний детерминированного конечного автомата (ДКА), возвращающийся в исходное состояние. Если из состояния $q$ можно вернуться в $q$ ненулевой последовательностью входных символов, то $q$ называется циклическим состоянием. Понятие тесно связано с классом неразрешимых задач: задача о том, зациклится ли алгоритм (машина Тьюринга) на заданном входе, называется проблемой остановки и неразрешима в общем случае — это доказано Аланом Тьюрингом в 1936 году.

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

Цикл в программировании

В императивном программировании цикл — это управляющая конструкция, многократно исполняющая блок операторов. Основные виды:

  • while — цикл с предусловием: тело выполняется, пока условие истинно;
  • for — цикл со счётчиком: выполняется заданное число раз или по изменению переменной;
  • do...while — цикл с постусловием: тело выполняется хотя бы один раз;
  • foreach — перебор элементов коллекции.

Пример цикла на Python:

``python i = 0 while i < 10: print(i) i += 1 ``

Бесконечный цикл возникает, если условие выхода никогда не выполняется:

``python while True: pass ``

В языках с управлением потоком исполнения бесконечный цикл может прерываться операторами break, continue, return или исключениями. В многозадачных системах бесконечный цикл без уступки процессора (например, без вызова функций ожидания) приводит к «зависанию» программы и перегрузке процессора.

Цикл в математике

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

Цикл в физике и инженерии

В термодинамике цикл — это последовательность процессов, возвращающая систему в исходное состояние. Известны циклы Карно, Отто, Дизеля, Стирлинга. КПД теплового цикла определяется разностью температур нагревателя и холодильника. В электротехнике циклом называют периодическое изменение величины, например, цикл переменного тока.

Интересные факты

  • Задача остановки была одним из семи проблем Гильберта, сформулированных в 1928 году; её неразрешимость, доказанная Тьюрингом, стала одним из фундаментальных результатов математической логики.
  • В языке C бесконечный цикл for(;;) считается идиоматическим способом записи вечного цикла.
  • В операционных системах планировщик процессов использует кванты времени: зацикленная программа получает управление снова и снова, но система не «зависает» благодаря прерываниям.

Источники

Заметили ошибку или не согласны с информацией в статье? Напишите нам support@bfometr.ru