АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Функція Геделя та її основна властивість

Читайте также:
  1. I. Основная форма: помешательство.
  2. II. Основная часть.
  3. III. Основная часть
  4. V. ОСНОВНАЯ ПРАКТИКА ЯСНОГО СВЕТА
  5. В. Раскрытие аргументов. Основная часть презентации
  6. Вектор-функція скалярного аргументу
  7. Виробництво та виробнича функція
  8. Вкладка Основная
  9. Властивість лінійності зображення
  10. Глобалізація як основна сучасна тенденція розвитку світової економіки
  11. Действие — основная единица анализа деятельности. Действие — это процесс, направленный на достижение цели.
  12. Дельта-функція

 

Функцiя Геделя G дозволяє кодувати одним натуральним числом довiльну скiнченну послiдовнiсть натуральних чисел. Функцiя Геделя визначається так:

G (x, y) = mod (l (x), 1+(y +1) × r (x)).

 

Отже, функція G є ПРФ.

Теорема (про основну властивість функції Геделя). Для довiльної скiнченної послiдовностi натуральних чисел b0, b 1 ,..,bn знайдеться натуральне число t, таке, що G (t, i)= bi для всiх i Î{0,..., n }.

Індукцiєю по n доведемо твердження, відоме як китайська теорема про остачі:

Лeма. Для довiльних натуральних чисел b0, b 1 ,.., bn, для довiльних попарно взаємно простих чисел p0, p 1 ,.., pn, таких, що pi>bi для всiх i Î{0,..., n }, знайдеться натуральне число M, таке, що M < p 0 × ... × pn та mod (M,pi)= bi для всiх i Î{0,..., n }.

1) n =1. Для довiльних взаємно простих p, q

{ mod (i × p, q) | i Î{0,..., q -1}}={0,..., q -1}.

Справдi, для j, i таких, що q>j >i ³ 0, маємо mod (j × p, q) ¹ mod (i × p, q), iнакше (j - i) × p дiлиться на q, що суперечить взаємнiй простотi p та q. Тому для довiльних натуральних b 0, b 1 та для довiльних взаємно простих p 0, p 1, таких, що p 0 > b 0 та p 1 > b 1, iснують натуральнi a0, a1 такi, що a0 < p 0, a1 < p 1, mod (a1 × p 1, p 0) = b0 і mod (a0 × p 0, p 1)= b 1. Узявши k = =a0 × p 0 + a1 × p 1, маємо mod (k, p 0)= b 0 та mod (k, p 1) = b 1. Тодi M 1= mod (k, p 0 × p 1) - шукане M для випадку n =1. Справдi, M 1< p 0, p 1, mod (M 1, p 0)= b 0, mod (M 1, p 1)= b 1, бо k =a × p 0 × p 1 +M 1 для деякого aÎ N.

2) n = k Þ n = k +1. Нехай твердження леми правильне для n = k. Вiзьмемо n = k +1. Маємо натуральнi b 0, b 1 ,.., bk +1 тa попарно взаємно простi p 0, p 1 ,.., pk +1, такi, що pi>bi для всiх i Î{0,..., k+ 1}. Покладемо c 0= M 1, c 1 =b 2,..., ck=bk +1, q 0= p 0 × p 1, q 1= p 2,..., qk = pk +1. Тодi числа q 0, q 1 ,.., qk попарно взаємно простi та qi>ci для всiх i Î{0,..., k }, тому за припущенням iндукцiї знайдеться натуральне число M, таке: M < q 0 × q 1 × ... × qk та mod (M, qi)= ci для всiх i Î{0,..., k }. Звiдси дістаємо M < p 0 × ... × pk+ 1, mod (M,pi)= bi для всiх i Î{0,..., k+ 1} та mod (M, p 0 × p 1)= M 1. Останнє означає, що M =a × p 0 × p 1 +M 1 для деякого aÎ N. Звiдси mod (M 1, p 0)= mod (M, p 0)= b 0 та mod (M 1, p 1)= mod (M, p 1)= b 1.

Отже, твердження леми правильне i для n = k +1.

Доводимо тепер теорему. Знайдемо числа M та b такi, що t = C (M, b) - шукане, тобто G (t,i)= mod (М, 1+(і +1) × b))= bi для всiх i Î{0,..., n }.

Покладемо b =(1+ n + b 0+...+ bn)!. Залишилось знайти число M. Позначимо pi =1+(і +1) × b. Тодi pi>bi для всiх i Î{0,..., n }. Крiм того, числа p0, p 1 ,.., pn попарно взаємно простi. Справдi, припустимо супротивне: iснує просте q >1, таке, що для деяких i, j, таких, що j>i, числа pi та pj дiляться на q. Тодi pi - pj =(j - i) × b дiлиться на q. Але j - i < n, тому j - i входить як множник у число b, звiдки i дiлиться на q, тобто b = g × q для деякого gÎ N. Звiдси числа pi =1+(і +1) × g × q та pj =1+(j +1) × g × q не дiляться на q, a це суперечить припущенню.

Умови леми виконанi, тому знайдеться натуральне число M, таке, що M < p 0 × ... × pn і mod (M,pi)= mod (М, 1+(і +1) × b))= bi для всiх i Î{0,..., n }.

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)