Рекурсивные функции - История изменений

217.66.159.116: Перенаправление на Примитивно рекурсивные функции

2017-01-15T14:12:18Z

Перенаправление на Примитивно рекурсивные функции

Внесённые изменения

194.85.161.2: /* Теорема о примитивной рекурсивности вычислимых функций */

2013-01-19T21:52:32Z

‎Теорема о примитивной рекурсивности вычислимых функций

194.85.161.2: /* Теорема о примитивной рекурсивности вычислимых функций */

2013-01-19T21:50:39Z

‎Теорема о примитивной рекурсивности вычислимых функций

194.85.161.2 в 21:49, 19 января 2013

2013-01-19T21:49:19Z

194.85.161.2: /* Теорема о примитивной рекурсивности вычислимых функций */

2013-01-19T21:48:44Z

‎Теорема о примитивной рекурсивности вычислимых функций

194.85.161.2: /* Теорема о примитивной рекурсивности вычислимых функций */

2013-01-19T21:43:01Z

‎Теорема о примитивной рекурсивности вычислимых функций

194.85.161.2 в 21:39, 19 января 2013

2013-01-19T21:39:12Z

194.85.161.2: /* Теорема о примитивной рекурсивности вычислимых функций */

2013-01-19T21:36:27Z

‎Теорема о примитивной рекурсивности вычислимых функций

194.85.161.2: /* Теорема о примитивной рекурсивности вычислимых функций */

2013-01-19T21:35:44Z

‎Теорема о примитивной рекурсивности вычислимых функций

194.85.161.2: /* Теорема о рекурсии */

2013-01-19T21:03:39Z

‎Теорема о рекурсии

Внесённые изменения

@@ Строка 125: / Строка 125: @@
 == Теорема о примитивной рекурсивности вычислимых функций ==
 {{Теорема
-|statement= Если для  вычислимой функции <tex> F </tex> существует примитивно рекурсивная функция <tex> T </tex>, такая что для любых аргументов <tex> args </tex> максимальное количество шагов, за которое будет посчитана <tex> F(x) </tex>  на [[Машина Тьюринга|МТ]] равно  <tex> T(args) </tex>, то <tex> F </tex>  примитивно рекурсивная функция.
+|statement= Если для  [[Вычислимые функции|вычислимой функции]] <tex> F </tex> существует примитивно рекурсивная функция <tex> T </tex>, такая что для любых аргументов <tex> args </tex> максимальное количество шагов, за которое будет посчитана <tex> F(x) </tex>  на [[Машина Тьюринга|МТ]] равно  <tex> T(args) </tex>, то <tex> F </tex>  примитивно рекурсивная функция.
 |proof=
 Каждому состоянию MT поставим в соответствие список из четырех чисел <tex> [L,R,S,C] </tex>, где:

@@ Строка 125: / Строка 125: @@
 == Теорема о примитивной рекурсивности вычислимых функций ==
 {{Теорема
-|statement= Если для  вычислимой функции <tex> F </tex> существует примитивно рекурсивная функция <tex> T </tex>, такая что для любых аргументов <tex> args </tex> максимальное количество шагов, за которое будет посчитана <tex> F(x) </tex>  на [[Машина Тюринга|МТ]] равно  <tex> T(args) </tex>, то <tex> F </tex>  примитивно рекурсивная функция.
+|statement= Если для  вычислимой функции <tex> F </tex> существует примитивно рекурсивная функция <tex> T </tex>, такая что для любых аргументов <tex> args </tex> максимальное количество шагов, за которое будет посчитана <tex> F(x) </tex>  на [[Машина Тьюринга|МТ]] равно  <tex> T(args) </tex>, то <tex> F </tex>  примитивно рекурсивная функция.
 |proof=
 Каждому состоянию MT поставим в соответствие список из четырех чисел <tex> [L,R,S,C] </tex>, где:

← Предыдущая		Версия 21:49, 19 января 2013
Строка 1:		Строка 1:
−	~~{{В разработке}}~~
	Все рассматриваемые здесь функции действуют из подмножества <tex> \mathbb {N}^t </tex> в <tex> \mathbb {N} </tex>, где <tex> t </tex> - любое натуральное число.Также будем считать что <tex> 0</tex> натуральное число.		Все рассматриваемые здесь функции действуют из подмножества <tex> \mathbb {N}^t </tex> в <tex> \mathbb {N} </tex>, где <tex> t </tex> - любое натуральное число.Также будем считать что <tex> 0</tex> натуральное число.
	== Основные определения ==		== Основные определения ==

@@ Строка 126: / Строка 126: @@
 == Теорема о примитивной рекурсивности вычислимых функций ==
 {{Теорема
-|statement= Если для  вычислимой функции <tex> F </tex> существует примитивно рекурсивная функция <tex> T </tex>, такая что для любых аргументов <tex> args </tex> максимальное количество  за которое будет посчитана <tex> F(x) </tex>  на [[Машина Тюринга|МТ]] равно  <tex> T(args) </tex>, то <tex> F </tex>  примитивно рекурсивная функция.
+|statement= Если для  вычислимой функции <tex> F </tex> существует примитивно рекурсивная функция <tex> T </tex>, такая что для любых аргументов <tex> args </tex> максимальное количество шагов, за которое будет посчитана <tex> F(x) </tex>  на [[Машина Тюринга|МТ]] равно  <tex> T(args) </tex>, то <tex> F </tex>  примитивно рекурсивная функция.
 |proof=
-Каждому состоянию MT поставим в соответствие список из четырех чисел [L,R,S,C],где
+Каждому состоянию MT поставим в соответствие список из четырех чисел <tex> [L,R,S,C] </tex>, где:
-<tex> L </tex> - состояние MT слева от головки ленты, представлено в виде числа в системы счисления с основанием равным алфавиту MT. о записано слева направо. Пробелу соответствует ноль, чтобы число было конечным.
+<tex> L </tex> - состояние MT слева от головки ленты, представлено в виде числа в системы счисления с основанием равным алфавиту MT. Младшие разряды находятся возле головки. Пробелу соответствует ноль, чтобы число было конечным.
-<tex> R </tex> - состояние MT справа от головки, представлено аналогично <tex> L </tex> только число записано справа налево.
+<tex> R </tex> - состояние MT справа от головки, представлено аналогично <tex> L </tex> только возле головки МТ находятся старшие разряды.
 <tex> S </tex> - номер текущего состояния
@@ Строка 139: / Строка 139: @@
 Тогда всем переходам соответствует функция <tex> f([L,R,S,C]) </tex> принимающая состояние МТ и возвращающая новое состояние.
-Покажем что она примитивно рекурсивная . При применении перехода в <tex> C </tex> записывается новый символ,затем из-за сдвига головки в <tex> L </tex> и <tex> R </tex> в конец добавляется новая цифра или удаляется старая, затем в <tex> C </tex>  записываетcя символ после сдвига, и в конце перехода в <tex> S </tex> записывается новое состояние автомата. Операции добавления в конец цифры или удаления последней цифры легко выражаются через простые арифметические операции, следовательно они примитивно рекурсивные. Все остальные операции являются простыми операциями над списками, а значит они тоже примитивно рекурсивные. Из этого следует что применения перехода {{---}} примитивно рекурсивная функция. В силу того что нужный переход можно выбрать используя конечное число функций if следует что и <tex> f </tex> также является примитивно рекурсивной функцией.
+Покажем что она примитивно рекурсивная . При применении перехода в <tex> C </tex> записывается новый символ,затем из-за сдвига головки в <tex> L </tex> и <tex> R </tex> в конец добавляется новая цифра или удаляется старая, затем в <tex> C </tex>  записываетcя символ после сдвига, и в конце перехода в <tex> S </tex> записывается новое состояние автомата. Операции добавления в конец цифры или удаления последней цифры легко выражаются через простые арифметические операции, следовательно они примитивно рекурсивные. Все остальные операции являются простыми операциями над списками, а значит они тоже примитивно рекурсивные. Из этого следует что применения перехода {{---}} примитивно рекурсивная функция. В силу того что нужный переход можно выбрать используя конечное число функций <tex> if </tex> следует что и <tex> f </tex> также является примитивно рекурсивной функцией.
 Функции преобразование аргументов в формат входных данных для МТ и получения ответа по состоянию МТ также выражаются через простые арифметические операции а значит они примитивно рекурсивные. Назовем их <tex> IN </tex> и  <tex> OUT </tex>.
@@ Строка 148: / Строка 148: @@
 <tex> N([L,R,S,C],t) = [L,R,S,C] </tex>
-<tex> N([L,R,S,C],t+1) = h([L,R,S,C],t+1,N([L,R,S,C],t)) </tex> , где h([L,R,S,X],y,[L1,R1,S1,C1]) = f([L1,R1,S1,C1]) </tex>
+<tex> N([L,R,S,C],t+1) = h([L,R,S,C],t+1,N([L,R,S,C],t)) </tex> , где <tex> h([L,R,S,X],y,[L1,R1,S1,C1]) = f([L1,R1,S1,C1]) </tex>
 Вместо <tex> t </tex> подставим <tex> T(args) </tex> и в итоге получим что <tex> F(args) = OUT(N(IN(args),T(args))) </tex> - примитивно рекурсивная функция.
 }}

@@ Строка 126: / Строка 126: @@
 == Теорема о примитивной рекурсивности вычислимых функций ==
 {{Теорема
-|statement= Если для  вычислимой функции <tex> F </tex> существует примитивно рекурсивная функция <tex> T </tex>, такая что для любых аргументов <tex> args </tex> максимальное количество  за которое будет посчитана <tex> F(x) </tex>  на [[MT|Машина Тюринга]] равно  <tex> T(args) </tex>, то <tex> F </tex>  примитивно рекурсивная функция.
+|statement= Если для  вычислимой функции <tex> F </tex> существует примитивно рекурсивная функция <tex> T </tex>, такая что для любых аргументов <tex> args </tex> максимальное количество  за которое будет посчитана <tex> F(x) </tex>  на [[Машина Тюринга|МТ]] равно  <tex> T(args) </tex>, то <tex> F </tex>  примитивно рекурсивная функция.
 |proof=
 Каждому состоянию MT поставим в соответствие список из четырех чисел [L,R,S,C],где
@@ Строка 139: / Строка 139: @@
 Тогда всем переходам соответствует функция <tex> f([L,R,S,C]) </tex> принимающая состояние МТ и возвращающая новое состояние.
-Покажем что она примитивно рекурсивная . При применении перехода в <tex> C </tex> записывается новый символ,затем из-за сдвига головки в <tex> L </tex> и <tex> R </tex>, в конец добавляется новая цифра или удаляется старая, затем в <tex> C </tex>  записываетcя символ после сдвига, и в конце перехода в <tex> S </tex> записывается новое состояние автомата. Операции добавления в конец цифры или удаления последней цифры легко выражаются через простые арифметические операции, следовательно они примитивно рекурсивные. Все остальные операции являются простыми операциями над списками, а значит они тоже примитивно рекурсивные. Из этого следует что применения перехода {{---}} примитивно рекурсивная функция. В силу того что нужный переход можно выбрать используя конечное число функций if следует что и <tex> f </tex> также является примитивно рекурсивной функцией.
+Покажем что она примитивно рекурсивная . При применении перехода в <tex> C </tex> записывается новый символ,затем из-за сдвига головки в <tex> L </tex> и <tex> R </tex> в конец добавляется новая цифра или удаляется старая, затем в <tex> C </tex>  записываетcя символ после сдвига, и в конце перехода в <tex> S </tex> записывается новое состояние автомата. Операции добавления в конец цифры или удаления последней цифры легко выражаются через простые арифметические операции, следовательно они примитивно рекурсивные. Все остальные операции являются простыми операциями над списками, а значит они тоже примитивно рекурсивные. Из этого следует что применения перехода {{---}} примитивно рекурсивная функция. В силу того что нужный переход можно выбрать используя конечное число функций if следует что и <tex> f </tex> также является примитивно рекурсивной функцией.
 Функции преобразование аргументов в формат входных данных для МТ и получения ответа по состоянию МТ также выражаются через простые арифметические операции а значит они примитивно рекурсивные. Назовем их IN и OUT.
 Рассмотрим функцию двух аргументов <tex> N([L,R,S,C],t) </tex> которая принимает состояние MT , число шагов <tex> t </tex> и возвращает состояние MT после <tex> t </tex> шагов.
 Покажем что N - примитивно рекурсивная функция.
 <tex> N([L,R,S,C],t) = [L,R,S,C] </tex>
 <tex> N([L,R,S,C],t+1) = h([L,R,S,C],t+1,N([L,R,S,C],t)) </tex> , где h([L,R,S,X],y,[L1,R1,S1,C1]) = f([L1,R1,S1,C1]) </tex>
-Подставим вместо <tex> t </tex> T(args) и в итоге получим что F(args) = OUT(N(IN(args),T(args))) - примитивно рекурсивная функция.
 }}

@@ Строка 1: / Строка 1: @@
 {{В разработке}}
 Все рассматриваемые  здесь функции действуют из подмножества <tex> \mathbb {N}^t </tex> в <tex> \mathbb {N} </tex>, где <tex> t </tex> - любое натуральное число.Также будем считать что <tex> 0</tex> натуральное число.
-== Примитивно рекурсивные функции ==
+== Основные определения ==
 Рассмотрим следующие правила преобразования функций:
@@ Строка 25: / Строка 24: @@
 В дальнейшем вместо <tex> P_{n,k}(x_1,\ldots,x_k) </tex> будем писать просто <tex> x_k </tex>, подразумевая требуемое нам <tex> n </tex>.
-=== Арифметические операции на примитивно рекурсивных функциях ===
+== Арифметические операции на примитивно рекурсивных функциях ==
-==== ''' n '''-местный ноль ====
+=== ''' n '''-местный ноль ===
 <tex> \textbf 0 </tex> - функция нуля аргументов.
@@ Строка 46: / Строка 45: @@
 <tex> \textbf M^n </tex> - n местная константа, получается аналогичным к <tex> \textbf 0^n </tex>  образом.
-==== Сложения ====
+=== Сложения ===
 <tex> sum(x,0) = x </tex>
 <tex> sum(x,y+1) = h(x,y,sum(x,y)) </tex> , где <tex> h(x,y,z)=I(z) </tex>
-==== Умножения ====
+=== Умножения ===
 <tex> prod(x,0) = \textbf 0^1(x) </tex>
 <tex> prod(x,y+1) = h(x,y,prod(x,y)) </tex>, где <tex> h(x,y,z)=sum(x,z) </tex>
-==== Вычитания ====
+=== Вычитания ===
 Если <tex> x < y </tex>, то <tex> sub(x,y) = 0 </tex> , иначе <tex> sub(x,y) = x - y </tex>.
@@ Строка 71: / Строка 70: @@
 <tex> sub(x,y+1) = h(x,y,sub(x,y)) </tex>, где <tex>  h(x,y,z) =sub_1(z) </tex>
-==== Операции сравнения ====
+=== Операции сравнения ===
 <tex> eq(x,y) = 1 </tex> если <tex> x = y </tex>, иначе <tex> eq(x,y) = 0 </tex>
@@ Строка 91: / Строка 90: @@
 <tex> lower(x,y) = mul(le(x,y),le(I(x),y)) </tex>
-==== IF ====
+=== IF ===
 <tex> if(0,x,y) = y </tex>
 <tex> if(c+1,x,y) = h(c,x,y,if(c,x,y)) </tex> , где <tex> h(c,x,y,d) = x </tex>
-==== Деление ====
+=== Деление ===
 <tex> divide(x,y) = \lfloor {\frac{x}{y}} \rfloor </tex>, если <tex> y > 0 </tex>. Если же <tex> y = 0 </tex>, то <tex> divide(x,0) </tex> и все связанные с делением функции равны каким то ,не интересными для нас, числами.
@@ Строка 120: / Строка 119: @@
 <tex> mod(x,y) = sub(x,mul(y,divide(x,y))) </tex>
-==== Работа со списками фиксированной длины====
+=== Работа со списками фиксированной длины===
 С помощью описанных выше арифметических операций можно выразить проверку на простоту числа и поиск <tex> n </tex> - того простого числа.
 Рассмотрим список из натуральны чисел <tex> [x_1,\ldots,x_n] </tex>, тогда ему в соответствия можно поставить число <tex> p_1^{x_1+1} \cdot p_2^{x_2+1} \cdot \ldots \cdot p_n^{x_n+1} </tex>, где <tex> p_i - i</tex>-тое простое число. Как видно из представления,создания списка, взятие <tex> i </tex> - того
 элемента и остальные операции являются простыми арифметическими операциями, а следовательно примитивно рекурсивными. Поэтому будем считать что у примитивно рекурсивной функций аргументы и результат могут быть списками из натуральных чисел.
-=== Теорема о примитивной рекурсивности вычислимых функций ===
+== Теорема о примитивной рекурсивности вычислимых функций ==
 {{Теорема
 |statement= Если для  вычислимой функции <tex> F </tex> существует примитивно рекурсивная функция <tex> T </tex>, такая что для любых аргументов <tex> args </tex> максимальное количество  за которое будет посчитана <tex> F(x) </tex>  на [[MT|Машина Тюринга]] равно  <tex> T(args) </tex>, то <tex> F </tex>  примитивно рекурсивная функция.