Cтраница 1
Бесконечный автомат, внутренняя структура которого представляет собой магазинную память. [1]
Фишера Многоленточные и бесконечные автоматы ( Киберн. [2]
Плетнев, 1985 ] Плетнев A.M. Поведение конечных и бесконечных автоматов в игровых ситуациях / / Автоматика и телемех. [3]
Для недетерминированных конечных, а также для недетерминированных и детерминированных бесконечных автоматов также существует единственный с точностью до изоморфизма состояний приведенный автомат. В первом случае отыскание этого автомата аналогично рассмотренному случаю конечных автоматов, а во втором его построение, вообще говоря, не является эффективным. Отсюда следует отсутствие эффективного способа описания множества приведенных автоматов по заданному стохастич. [4]
Если множество Q конечно, то автомат А называется конечным автоматом, в противном случае А - бесконечный автомат. Все реальные автоматы являются конечными. Именно они будут объектом дальнейшего изучения. Тем не менее это не означает отказа от рассмотрения в некоторых случаях автоматов с произвольным, в том числе и с бесконечным числом состояний. [5]
Если множество S конечно, то автомат А называется конечным автоматом, в противном случае А - бесконечный автомат. Все реальные автоматы являются конечными. [6]
Возвращаясь к базам данных, отметим, что каждый универсальный автомат Atm 2) ( & -, С /, V) является бесконечным автоматом - здесь бесконечна алгебра запросов U. Однако соответствующий точный автомат может быть и конечным. [7]
Первый тип автомата, который мы кратко рассмотрели ( машины Тьюринга), имеет конечное число элементов и является автоматом с конечным числом состояний, но, строго говоря, он представляет собой бесконечный автомат, так как длина ленты, с которой он оперирует, не определена и она может непрерывно вводиться в машину в течение неограниченного времени. В противоположность этому второй тип автоматов, к рассмотрению которого мы сейчас перейдем, является принципиально конечным. [8]
Другая возможная модификация понятия абстрактного конечного автомата возникает, если разбивать множество допустимых значений параметров, описывающих работу реального устройства, не на конечное, а на бесконечное число классов. В этой ситуации приходим к так называемому абстрактному бесконечному автомату St ( Л, Q, В, р, г), где A, Q, В - уже, вообще говоря, бесконечные множества входных символов, состояний и выходных символов, р и vp - функции переходов и выходов, p: QXA - - Q; ty: QxA - - B. Увеличение мощности алфавитов расширяет вычислительные возможности автоматов. Так, например, если конечные автоматы реализуют ограниченно-детерминированные функции ( см. § 1 гл. [9]
Изучение поведения характеристик стоимости вычисления в схемах позволяет увидеть различные взаимосвязи в процессе динамики вычисления, оценить возможность размена одной характеристики другой. Примером такого размена при изучении динамики вычисления на бесконечных автоматах служит размен времени на память, точнее, временных и емкостных сигнализирующих. [10]
В работе [3] подробно проанализированы типы операционных автоматов, возникающие при описании в терминах дискретных преобразователей устройств вычислительной машины. При этом оказалось, что операционное устройство вычислительной машины удобно рассматривать как бесконечный автомат специального вида. [11]
Описанный выше стандартный прием действительно позволяет ( с учетом сделанных замечаний относительно пустого слова) свести общую задачу синтеза автоматов к канонической задаче. Что же касается последней задачи, то она всегда имеет решение в силу предложения 4.2. Однако такое решение ( основанное на результатах § 2) не может нас удовлетворить, поскольку оно приводит к построению, вообще говоря, бесконечного автомата даже в тех случаях, когда существует дающий решение задачи конечный автомат. [12]
Во всех случаях SB и считаются конечными алфавитами, Q может быть конечным или бесконечным. ЭВМ и мозг, имеющие чрезвычайно большое, но конечное число внутренних: состояний, могут рассматриваться как конечные автоматы. Бесконечные автоматы представляют собой математическую идеализацию, возникающую из представления об автомате с конечным, но необозримо большим числом состояний. При этом имеется в виду лишь потенциальная бесконечность памяти, проявляющаяся в том, что память, хотя и остается конечной в некоторый момент времени, может неограниченно возрастать. Структурно растущий автомат представляется в виде соединения элементов, способных к размножению и наращиванию структуры. Современные ЭВМ можно рассматривать как растущие автоматы ( а вместе с тем и потенциально бесконечные) так как теоретически допускается возможность безграничного наращивания внешней памяти. [13]
Другая возможная модификация понятия абстрактного конечного автомата возникает, если разбивать множество допустимых значений параметров, описывающих работу реального устройства, не на конечное, а на бесконечное число классов. В этой ситуации приходим к так называемому абстрактному бесконечному автомату St ( Л, Q, В, р, г), где A, Q, В - уже, вообще говоря, бесконечные множества входных символов, состояний и выходных символов, р и vp - функции переходов и выходов, p: QXA - - Q; ty: QxA - - B. Увеличение мощности алфавитов расширяет вычислительные возможности автоматов. Так, например, если конечные автоматы реализуют ограниченно-детерминированные функции ( см. § 1 гл. Более того, с помощью бесконечных автоматов может быть описано функционирование остальных, модификаций понятия автомата. Вместе с тем большая общность понятия бесконечного автомата снижает его содержательное значение, так что в основном изучаются лишь специальные подклассы бесконечных автоматов, связанные с конкретными моделями управляющих систем. [14]
Другая возможная модификация понятия абстрактного конечного автомата возникает, если разбивать множество допустимых значений параметров, описывающих работу реального устройства, не на конечное, а на бесконечное число классов. В этой ситуации приходим к так называемому абстрактному бесконечному автомату St ( Л, Q, В, р, г), где A, Q, В - уже, вообще говоря, бесконечные множества входных символов, состояний и выходных символов, р и vp - функции переходов и выходов, p: QXA - - Q; ty: QxA - - B. Увеличение мощности алфавитов расширяет вычислительные возможности автоматов. Так, например, если конечные автоматы реализуют ограниченно-детерминированные функции ( см. § 1 гл. Более того, с помощью бесконечных автоматов может быть описано функционирование остальных, модификаций понятия автомата. Вместе с тем большая общность понятия бесконечного автомата снижает его содержательное значение, так что в основном изучаются лишь специальные подклассы бесконечных автоматов, связанные с конкретными моделями управляющих систем. [15]