Алгоритм: определение и основные свойства. Классические машины Тьюринга. Тезис Тьюринга icon

Алгоритм: определение и основные свойства. Классические машины Тьюринга. Тезис Тьюринга



НазваниеАлгоритм: определение и основные свойства. Классические машины Тьюринга. Тезис Тьюринга
Дата конвертации22.05.2013
Размер29.33 Kb.
ТипДокументы
источник
1. /Экзамены-2/АлгоритмВопросы.doc
2. /Экзамены-2/АлгоритмТеорема.doc
3. /Экзамены-2/БилГраф.doc
4. /Экзамены-2/Задачи-МТ.doc
5. /Экзамены-2/Тест 1-25.doc
6. /Экзамены-2/ЭкзБилДисМат2.doc
7. /Экзамены-2/ЭкзГраф.doc
8. /Экзамены-2/задачи по графом 2007.doc
Алгоритм: определение и основные свойства. Классические машины Тьюринга. Тезис Тьюринга
Любой алгоритм можно преобразовать в машину Тьюринга
Алгоритм Зыкова
Этюд Реализация на машине Тьюринга задачи сортировки слова по возрастанию в алфавите {0,1,2}. Этюд
Тест Этюд Реализация на машине Тьюринга задачи сортировки слова по возрастанию в алфавите {0,1,2}. Этюд
Задача. Экзаменатор
1. Дайте полный список проведенных игр, соответствующий графу на рис. 3
Вопросы и задачи

Алгоритм: определение и основные свойства. Классические машины Тьюринга. Тезис Тьюринга.


Машина Тьюринга: принцип действия, описание работы. Построение алгоритмов для реализации на машинах Тьюринга.


Универсальные машины. Первая теорема Шеннона. Вторая теорема Шеннона.


Нормальные алгоритмы и тезис Маркова. Преобразование машин Тьюринга в нормальные алгоритмы.


Понятие алгоритмической разрешимости. Задачи об остановке и печати машин Тьюринга. Самоанализирующие машины Тьюринга.


Алгорифмическая неразрешимость задачи об остановке машины Тьюринга при произвольном входном слове.


Алгорифмическая неразрешимость задачи об остановке машины Тьюринга на пустой ленте.


Алгорифмическая неразрешимость задачи о печатании символа точно один раз.


Алгорифмическая неразрешимость задачи о печатании символа бесконечно много раз.


Алгорифмическая неразрешимость задачи о печатании символа хотя бы один раз.


Тезис Маркова. Нормальные алгоритмы.


Преобразование машин Тьюринга в нормальные алгоритмы.


Понятие эффективной перечислимости. Эффективное распознавание и теорема Поста. Перечисление останавливающихся машин.


Эффективная перечислимость машин Тьюринга.


Эффективная перечислимость нормальных алгоритмов.


Теорема Поста (эффективная распознаваемость подмножества эффективно перечислимого множества).


Эффективная перечислимость останавливающихся машин Тьюринга и невозможность эффективного перечисления не останавливающихся машин Тьюринга.


Сведение числовых систем к натуральным числам. Равномощные множества и кардинальные числа. Парадокс Галилея и трансфинитные числа. Конечные, счетно-бесконечные и несчетные множества чисел.


Счетность множества натуральных, целых, рациональных и алгебраических чисел. Несчетность множества трансцидентных, действительных и комплексных чисел.

Вычислимые действительные числа. Вычислимость алгебраических и существование вычислимых трансцидентных чисел. Невычислимые числа.


Несчетность множества арифметических функций. Вычислимые арифметические функции. Невычислимые функции.


Счетность множества вычислимых арифметических функций.


Невозможность эффективного перечисления и сравнения вычислимых арифметических функций.


Невычислимые функции. Невозможность эффективного распознавания функций-констант среди вычислимых арифметических функций.


Несчетность множества частичных арифметических функций. Вычислимые частичные арифметические функции и их эффективное перечисление.


Невычислимые частичные функции. Теорема Черча (невозможность эффективного распознавания точек неопределенности вычислимой частичной функции).


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


Примитивно-рекурсивные функции и базис Клини. Примитивная рекурсивность суммы и факториала.


Рекурсивная функция. Примитивная рекурсивная функция. Базис Клини.


Геделева нумерация и эффективная перечислимость примитивно-рекурсивных функций.


Общерекурсивные и частично-рекурсивные функции. Расширенный базис Клини. Частичная рекурсивность разности.


Гёделева нумерация и эффективная перечислимость частично-рекурсивных функций.


Частичная рекурсивность нигде не определенной функции и функции, определенной в одной точке.


Тезис Черча. Расширенный базис Клини. Частичная рекурсивность разности.


Частичная рекурсивность нигде не определенной функции и функции, определенной в одной точке.


Рекурсивные функции и невозможность их эффективного перечисления.


Невозможность эффективной распознаваемости примитивно рекурсивных функций среди рекурсивных. Непримитивно рекурсивные функции.


Невозможность эффективной распознаваемости рекурсивных функций среди частично-рекурсивных. Нерекурсивные функции.




Похожие:

Алгоритм: определение и основные свойства. Классические машины Тьюринга. Тезис Тьюринга iconАлгоритм: определение и основные свойства. Классические машины Тьюринга. Тезис Тьюринга
Машина Тьюринга: принцип действия, описание работы. Построение алгоритмов для реализации на машинах Тьюринга
Алгоритм: определение и основные свойства. Классические машины Тьюринга. Тезис Тьюринга iconУстройство Машины Тьюринга
В состав Машины Тьюринга входит бесконечная в обе стороны лента, разделённая на ячейки, и управляющее устройство, способное находится...
Алгоритм: определение и основные свойства. Классические машины Тьюринга. Тезис Тьюринга iconКонкурс «Мой помощник компьютер» Этап II. Задача Задана таблица-программа некоторой машины Тьюринга. Проанализируйте её и сформулируйте задачу, которая решается этой программой
Задана таблица-программа некоторой машины Тьюринга. Проанализируйте её и сформулируйте задачу, которая решается этой программой
Алгоритм: определение и основные свойства. Классические машины Тьюринга. Тезис Тьюринга iconКонкурс «Мой помощник компьютер» Этап II. Задача Сформулируйте сами задачу для построения машины Тьюринга. Решите её. Опубликуйте свою задачу (без решения) на форуме конкурса (
Тьюринга. Решите её. Опубликуйте свою задачу (без решения) на форуме конкурса (Форум Мой помощник компьютер II этап конкурса, тема...
Алгоритм: определение и основные свойства. Классические машины Тьюринга. Тезис Тьюринга iconЭтюд Реализация на машине Тьюринга задачи сортировки слова по возрастанию в алфавите {0,1,2}. Этюд
Этюд Реализация на машине Тьюринга задачи сортировки слова по возрастанию в алфавите {0,1,2}
Алгоритм: определение и основные свойства. Классические машины Тьюринга. Тезис Тьюринга iconСамостоятельная работа по теме «Алгоритмы: линейные и разветвляющиеся» в ариант 1 Дать определение понятиям: алгоритм, линейный алгоритм

Алгоритм: определение и основные свойства. Классические машины Тьюринга. Тезис Тьюринга iconТема урока. Алгоритм и его свойства. Исполнители алгоритмов
Алгоритм это описание некоторой последовательности действий, которую нужно совершить для достижения определенной цели
Алгоритм: определение и основные свойства. Классические машины Тьюринга. Тезис Тьюринга iconКонкурс «Мой помощник компьютер» Этап II. Задача Даны два натуральных числа n и m
Необходимо построить машину Тьюринга, которая на ленте оставит сумму чисел n и m (в унарной системе). Конечное положение автомата...
Алгоритм: определение и основные свойства. Классические машины Тьюринга. Тезис Тьюринга iconКонкурс «Мой помощник компьютер» Этап II. Задача 1
Входное слово состоит только из + и. Автомат (каретка) находится где-то слева от входного слова. Необходимо построить машину Тьюринга,...
Алгоритм: определение и основные свойства. Классические машины Тьюринга. Тезис Тьюринга iconКонкурс «Мой помощник компьютер» Этап II. Задача Дано натуральное число
Дано натуральное число n в восьмеричной системе счисления. Необходимо построить машину Тьюринга, которая увеличивала бы заданное...
Алгоритм: определение и основные свойства. Классические машины Тьюринга. Тезис Тьюринга iconАлгоритм, свойства алгоритма, исполнители алгоритмов Компьютер как формальный исполнитель алгоритмов
Алгоритм понятное и точное предписание исполнителю совершить последовательность действий, направленных на достижение указанной цели...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©lib2.podelise.ru 2000-2013
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы