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

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

Читайте также:
  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, b1, ..,bn знайдеться натуральне число t, таке, що G(t, i)=bi для всiх iÎ{0,..., n}.

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

Лeма. Для довiльних натуральних чисел b0, b1 ,.., bn , для довiльних попарно взаємно простих чисел p0, p1 ,.., pn , таких, що pi>bi для всiх iÎ{0,...,n}, знайдеться натуральне число M, таке, що M< p0×...×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льних натуральних b0, b1 та для довiльних взаємно простих p0, p1, таких, що p0 > b0 та p1 > b1, iснують натуральнi a0, a1 такi, що a0 < p0, a1 < p1, mod(a1×p1, p0) = b0 і mod(a0×p0, p1)=b1. Узявши k = =a0×p0 + a1×p1, маємо mod(k, p0)=b0 та mod(k, p1) = b1. Тодi M1=mod(k, p0×p1) - шукане M для випадку n=1. Справдi, M1< p0,p1, mod(M1, p0)=b0, mod(M1, p1)=b1, бо k=a×p0×p1+M1 для деякого aÎN.

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



Отже, твердження леми правильне 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+b0+...+bn)!. Залишилось знайти число M. Позначимо pi=1+(і+1)×b. Тодi pi>bi для всiх iÎ{0,...,n}. Крiм того, числа p0, p1 ,.., 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< p0×...×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.006 сек.)