Ср. Апр 17th, 2024

Коротко обсудим 3-ий подход к уточнению (конкретизации) понятия метода. По смыслу оно близко к идеям Тьюринга, но, в нем не употребляются представления о каких-то машинах. Метод задается системой подстановок, которые указывают, какие подмены знаков нужно создавать и в каком порядке эти подстановки должны следовать. Таковой подход был предложен А. А. Марковым. Сначала 50-х годов было введено понятие обычного метода (сам Марков называл их алгорифмами).

Вновь разглядим некий алфавит А, содержащий конечное число символов (букв). Введем ряд определений:

Слово — это неважно какая конечная последовательность символов алфавита

Число знаков в слове именуется его длиной.

Слово, длина которого равна нулю, именуется пустым.

Слово s именуется подсловом слова q, если q можно представить в виде q — rst, где rut- любые слова в том же алфавите (в том числе и пустые).

Сейчас можно найти понятие метода (не являющееся серьезным):

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

В методах Маркова в качестве простого шага метода принимается подстановка 1-го слова заместо другого. Пусть в алфавите А выстроено начальное слово Р, которое содержит подслово Рrобщем случае таких подслов в начальном слове может быть несколько), также имеется некое слово Pk в том же алфавите.

Подстановкой именуется подмена первого по порядку подслова Рr начального слова Р на слово Pk. Обозначается подстановка Рr→ Pk.

Метод в данной форме представления задается системой подстановок, которая представляет собой последовательность (перечень) подстановок. Если в этом перечне имеются подстановки с левыми частями, которые входят в Р, то 1-ая из их применяется к Р, в итоге чего оно перебегает в другое слово P1. К нему вновь применяется схема подстановок и т.д. Процесс прекращается в 2-ух случаях: или в перечне не нашлось подстановки с левой частью, входящей в Рn, или при получении Рn была использована последняя подстановка.

От content

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *