1. Синтаксис языка лисп. Списки. Атомы. Виды атомов. Комментарии

Скачать 260.62 Kb.

Название	1. Синтаксис языка лисп. Списки. Атомы. Виды атомов. Комментарии
страница	6/9
Тип	Документы

rykovodstvo.ru > Руководство эксплуатация > Документы

1 2 3 4 5 6 7 8 9

14. Нумерация алгоритмов и вычислимых функций

«Множество всех алгоритмов счётно.» ©

«Любую программу можно представить как последовательность 16-ричных чисел, склеить их и получить число и рассматривать как входные данные другой программы» © С машиной Тьюринга аналогично: любому символу можно поставить в соответствие код, а количество состояний — конечно.

Одну функцию могут реализовывать несколько алгоритмов (например a+b и b+a). Множество всех вычислимых функций меньше множества всех алгоритмов ⇒ можно пронумеровать.

15. Теорема параметризации

Пусть f(x,y) вычисляется по алгоритму P_f. Для фиксированного x=a получаем функцию g(y) = f(a, y), которая вычисляется по алгоритму P_g c индексом k(x). Существует функция k(x), которая по х даёт номер алгоритма P_g — т.е. на основе х автоматически строится алгоритм.

16. Понятие универсального алгоритма. Реализация на трёхленточной МТ

Универсальный алгоритм U(n, x): применяет к x алгоритм P_n и возвращает результат. Универсальный алгоритм существует! Строится трёхленточная МТ:

В начале входные данные, в конце — результат.
Текущее состояние МТ.
Правила МТ.

Если U существует, то мы можем с помощью одной вычислительной модели эмулировать любую другую МТ.
Проблемы, связанные с остановкой

Общерекурсивные программы не зацикливаются при любых аргументах. Зацикливающиеся программы не определены. Проблема — в невозможности перечисления общерекурсивных функций.

17. Проблема несчётности множества общерекурсивных функций

Общерекурсивная функция — частично рекурсивная функция, определённая для всех значений аргументов.
Множество всех общерекурсивных функций несчётно.
<�Доказательство>

{f₁, …, f_n} – множество всех общерекурсивных функций. Построим функцию g(n) = f_n(n)+1, g(n) отличается от любой общерекурсивной функции, однако сама является общерекурсивной, т.к. не зацикливается. Следовательно, множество всех общерекурсивных функций несчётно (их нельзя пронумеровать).

Пп. g(x)=f_n(x) | ∀x ⇒ x=n

f_n(n)+1 ≠ f_n(n)

</Доказательство>

18. Проблема определения общерекурсивности

Не существует алгоритма, который бы проверял, является ли поданная на вход функция общерекурсивной.

<�Доказательство>

Пусть g(m) =

1, если P_m общерекурсивна
0, если P_m необщерекурсивна

Построим функцию f(x), которая принимает себя на вход и прибавляет единицу.

f(x) =

P_x(x) + 1, если g(x) = 1 (P_x общерекурсивна)
0, если g(x) = 0

При нашем предположении f(x) никогда не зацикливается. f(x) = / переобозначим/

U(x, x) + 1, если g(x) = 1
0, если g(x) = 0

f(x) ≢ P_n(x) ← общ. рек. // f отличается от общерекурсивной

f(n) = U(n, n) + 1 = P_n(n) + 1 // f - общерекурсивна.

С одной стороны, f(x) общерекурсивная, с другой — отличается от общерекурсивной. Следовательно, предположение относительно g неверно, и функция g не существует.

</Доказательство>

19. Проблема самоприменимости

Невозможно создать программу, которая определяет, зацикливается ли программа P_n, если ей на вход подать саму себя.
Допустим, есть программа А, которая:

Принимает на входе программу P

Выполняет P(P)
Если P(P) напечатала “Hello World”, выводит“yes”, иначе “Hello World”

Проблема:

Вызываем А(А). Результат неизвестен. Такую программу реализовать нельзя.

<�Доказательство>

Путь существует функция f(n) =

1, если P_n самоприменима
0, если P_n не самоприменима

Отправим ей на вход G(n) :=

0, если f(n) = 0
цикл., если f(n) = 1

Если g самоприменима, то f=1 и g должна циклиться.

Предположение неверно, f(n) не существует.

</Доказательство>

1 2 3 4 5 6 7 8 9

Похожие:

	Дмитриев Михаил Николаевич гбоу школа №1586 \| Москва, Улица Дружбы... Проектная работа представляет собой программное приложение, разработанное как для уроков физики и химии, так и для индивидуальных...		1. Если атомы растворимого компонента в замещают в узлах решетки... Диаграмма состояния сплавов, образующих с ограниченной растворимостью в твердом состоянии с перитектикой, изображена на рис
	Семантика Синтаксис Морфология К 28 Семантика. Синтаксис. Морфология. — М.: Главная редакция восточной литературы издательства «Наука», 1988. — 309 с		Учебное пособие включает в себя материалы к 9 практическим занятиям... Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
	Методическое руководство к выполнению лабораторных работ по биоорганической... Скелет их молекул построен только из атомов углерода. В зависимости от последовательности соединения атомов углерода в углеродном...		Инструкция по составлению финансового отчета (краткие комментарии) № Основные требования к форме и составу документации, подтверждающей расход (Комментарии)
	Основная образовательная программа высшего образования Направление... Целью курса синтаксиса современного русского литературного языка является знакомство студентов с синтаксисом как центральной лингвистической...		Издание третье Панин, его стилистической системы, описана роль писателей, публицистов, общественных деятелей в развитии норм литературного языка....
	6. Злаки специального назначения Особую группу газонных злаков составляют виды, отличающиеся хорошей приспособленностью к специфическим условиям. Они могут быть использованы...		Урока: Образовательные Развить понятие о взаимном влиянии атомов, зависимости применения от свойств веществ
	Учебно-методическое пособие по английскому языку для студентов первого... Введение. Своеобразие английского языка. Его роль в современном мире как языка международного и межкультурного общения		Методическая разработка «Рекомендации по переводу научного текста» Деловой иностранный язык играет большую роль в процессе изучения иностранного языка в колледже. Деловой язык делает акцент на конкретные...
	Проблемная технология на уроках английского языка в 9 классе Автор: Закирова Татьяна Валерьевна Маоу «сош №7 с углубленным изучением английского языка» г. Перми, учитель английского языка высшей квалификационной категории		Сведения о чу дпо «Чувашский учебно-курсовой комбинат» Предмет и виды деятельности Учреждения, виды реализуемых образовательных программ
	Курсовая работа На тему: «клиника и лечение трихинеллеза» Экспериментально трихинеллезом заражаются все виды млекопитающих животных и многие виды птиц		«Углубленное изучение английского языка» по направлению подготовки... Повышение уровня культуры образования, а также культуры общения, мышления и речи. 3 Знакомство с культурой стран изучаемого языка...

Руководство, инструкция по применению