Цик — понятие теории вычислимости¶
Цик — это последовательность состояний вычислительной системы (алгоритма, программы, автоматической машины), которая повторяется периодически: система, начав с одного из состояний, возвращается к нему и далее проходит через ту же последовательность состояний бесконечно. Понятие цикла используется в теории алгоритмов, теории автоматов, теории вычислимости, а также в программировании, где циклом называют конструкцию повторного выполнения операторов программы.
¶Цикл в теории автоматов и алгоритмов
В теории автоматов цикл — это путь в графе состояний детерминированного конечного автомата (ДКА), возвращающийся в исходное состояние. Если из состояния $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(;;)считается идиоматическим способом записи вечного цикла. - В операционных системах планировщик процессов использует кванты времени: зацикленная программа получает управление снова и снова, но система не «зависает» благодаря прерываниям.
¶Источники
- Кнут Д. «Основы программирования»
- Тьюринг А. «On Computable Numbers» (1936)
- Гейнс Р. «Введение в теорию автоматов»
- Кормен Т. и др. «Алгоритмы: построение и анализ»
