Часть 3. Математические модели

О вычислимости целочисленных функций коллективами из двух автоматов

В. В. Ушакова

Московский государственный университет имени М. В. Ломоносова, механико-математический факультет

Аннотация: В данной работе исследуется вычислимость одноместных частичных функций счётнозначной логики коллективами автоматов. Найден класс функций, вычислимых коллективами из двух автоматов. Это периодические функции и простейшие линейные функции, которые, начиная с некоторого значения аргумента $x$ ведут себя, как функция $f(x) = x + C$. Показано, что класс одноместных частичных функций счётнозначной логики, вычислимых коллективами из трёх автоматов, является более широким.

Ключевые слова: вычислимость, автомат, коллективы автоматов, периодические функции.