Пример обобщения концепции машины Тьюринга Дипломник: Макаров А.А. Научный руководитель: проф. Граничин О.Н. СПбГУ, математико-механический факультет, - презентация

1 Пример обобщения концепции машины Тьюринга Дипломник: Макаров А.А. Научный руководитель: проф. Граничин О.Н. СПбГУ, математико-механический факультет, 2005 год.

2 Актуальность темы 1936г. Тьюринг –МТ абстрактное вычислительное устройство для мат. модели описания алгоритмов 1936г. Черч –Любой процесс, который естественным образом мог бы быть назван процедурой, реализуем МТ. В этом смысле МТ считается эквивалентом любого ВУ 2005г. 40 лет закону Мура –Число транзисторов на одной интегральной микросхеме удваивается каждые 18 мес. –Через несколько лет размер элементарной ячейки компьютера составит ангстрем –Новый вид носителей информации требует новых математических оснований

3 Существующие подходы Создание СБИС по все более высокоскоростной технологии Использование квантовых компьютеров для быстрого решения сложных задач с данными большой размерности

4 Классическая МТ MT = Программа для пары однозначно задает Алгоритм работы: в любой момент времени если машина останавливается, иначе выбираем и полагаем

5 Нестандартная МТ НМТ = Структура НМТ расширена двумя компонентами: - множество задания программы (где - множество всевозможных наборов ) т.е.,причем и - оператор эволюции состояний и памяти Алгоритм работы: в любой момент времени –если, то машина останавливается; –если, то происходит естественная эволюция –если,то в работу машины вмешивается внешнее воздействие: Здесь – время необходимое для перевода состояния и памяти машины из.

6 Набор моделей Пусть – это множество НМТ (набор моделей), т.е. каждая ячейка памяти представляет собой отдельное устройство Изменение состояния памяти может происходить непрерывно и параллельно во всех ячейках Такая система позволяет переосмыслить понятие такт, момент достижения определенного множества

7 Алгоритм решения диофантова уравнения 2003г. Тьен Д. Кью предложил квантовый алгоритм решения диофантова уравнения Уравнение –неотрицательные целые решения –глобальный минимум Набор моделей, для реализации алгоритма, который заключается в следующем: –Запускаем физический процесс H, соответствующий заданному диофантову уравнению на время T. Требуется найти основное состояние системы в момент времени T. –Повторяем временной процесс для получения статистических данных –Если ни одно из измеренных состояний не будет получено с вероятностью более ½, то увеличим T и вернемся к предыдущему шагу –В итоге, для некоторого T, одно из состояний будет получаться с высокой вероятностью. Оно будет основным состоянием системы, в котором получается глобальный минимум –Если энергия полученного основного состояния – ноль, то исследуемое диофантово уравнение имеет решение, и не имеет в противном случае. –При этом конечность времени T следует из квантовой адиабатической теоремы, которая утверждает, что система перейдет в наше искомое основное состояние за конечное время.

8 Результаты моделирования X-20=0 T=86 X+20=0 T=50

9 Заключение Рассмотренная модель вычислений позволяет описывать подавляющее большинство процессов, происходящих в реальном мире Работу различных вычислительных устройств (например, аналоговые компьютеры, биокомпьютеры, нейрокомпьютеры, квантовые компьютеры) Возникает задача создания языков и средств программирования, позволяющих описывать непрерывные процессы с переходами от одной вычислительной модели к другой