Главная    Почта    Новости    Каталог    Одноклассники    Погода    Работа    Игры     Рефераты     Карты
  
по Казнету new!
по каталогу
в рефератах

Алгоритмдер теориясы

;кез келген машинаның ішкі жағдайы болып табылады.

Егер Р - бос болуы мүмкін, ал Qбос емес сөз болса және - машинаның ішкі жағдайы болса, онда машинаның конфигурациясы деп аталады. Егер келесі шарттардың біреуі орындалса, онда машина aконфигурациясын bконфигурациясына көшіреді дейміз:

1)             aконфигурациясы  түрінде, bконфигурациясы  түрінде, ал - машинаның бұйрықтарының біреуі;

2)             a- түрінде, b- түрінде, ал - машинаның бұйрықтарының біреуі;

3)             a- түрінде, b- түрінде және - машинаның бұйрықтарының біреуі;

4)             a- түрінде, b- түрінде және - машинаның бұйрықтарының біреуі;

5)             a- түрінде, b- түрінде және - машинаның бұйрықтарының біреуі.

Егер -ден басталатын бұйрық болмаса, онда машина  конфигурациясында тоқтайды деп атаймыз.

Егер конфигурациясына енетін ішкі жағдай болса, кез келген 0 £і £m-1 шартын қанағаттандыратын і үшін машина  конфигурациясын  конфигурациясына көшірсе, ал  конфигурациясында тоқтаса, онда ақырлы  конфигурациялар тізбегі машинаның есептеуі деп аталады. Және   есептеуі -ден басталып, -мен аяқталады дейміз. Т машинаның  алгоритмін келесі түрде анықтаймыз:

(Р) =Qорындалуы үшін  конфигурациясынан басталып, =Qтеңдігі орындалатын  конфигурациясыменаяқталуы керек.

Ескерту.  сөздеріндегі  символдарын ескермейміз. Себебі барлық уақытта бұл символ бос квадратты білдіреді.

Енді натурал сандарға қолданылатын алгоритмдерге көшейік. Кез келген натурал mсанына m+1 - бірліктен тұратын тізбекті сәйкес қоямыз және оны  деп белгілейміз. Мысалы, 2-ге 111, 5-ке 111111. Егер кез келген сандары үшін  =  теңдігі орындалса, онда Тьюринг машинасы жартылай анықталған арифметикалық ¦() функциясын есептейді дейміз.

Берілген функцияны есептейтін Тьюринг машинасы табылса, ол функция Тьюринг бойынша есептеледі деп аталады.

Кез келген Тьюринг машинасын кез келген nсаннан тұратын тізбекке пайдалануға болады. Берілген ¦(х) функциясын есептейтін Тьюринг машинасына екі сан берсек, ол машина басқа функцияны есептейді.

Есептер

1.           ¦(х, у) = х +у функциясын есептейтін Тьюринг машинасын құрыңыздар.

2.           ¦(х) = 2х функциясын есептейтін Тьюринг машинасын құрыңыздар.

3.           ¦(х) = 5х функциясын есептейтін Тьюринг машинасын құрыңыздар.

4.            Екінші есептегі құрылған Тьюринг машинасына екі саннан тұратын тізбек берсек, қандай функцияны есептейді?

5.           Бірінші есептегі құрылған Тьюринг машинасына бір сан берсек, қандай функцияны есептейді?

 

6.3Черч тезисі, геделдік нөмірлеу

 

Әрине, алгоритмнің кез келген формализациясын алгоритмнің дәл анықтамасы екенін дәлелдеу мүмкін емес. Оны не қабылдауға,не қабылдамауға болады. Тьюрингтен бөлек математиктер де есептеуге болатын функциялардың анықтамаларын берді. Дегенімен, олардың барлығы Тьюринг анықтамасымен эквивалент болып шықты. Есімізге Клини, Пост, Марковтардың анықтауларын алсақ та жеткілікті. Сондықтан, осы формализациялардың кез келгенін алгоритмнің дәл анықтамасы ретінде алуға болады деп есептелінеді. Бұл ойды Черч айтқан болатын. Сонымен, өзара эквивалент екі сөйлемді келтірейін.

Черч тезисі.Есептеуге болатын функциялар жиыны Тьюринг машинасында есептелінетін функциялар жиынына тең.

Черч тезисі.Алгоритмі бар функцияны есептейтін Тьюринг машинасы бар.

Бұл эквивалент екі тезистің ешқайсысын дәлелдеу мүмкін емес. Себебі, ол үшін алгоритмнің дәл анықтамасы карек. Бұл тезиске келіспеген математиктердің Тьюринг машинасы есептемейтін алгоритм табуға тырысқан еңбектерінен ештеңе шықпады. Сондықтан, қазіргі заманда Черч тезисімен келіспеген математиктер қалмады деуге болады.

Кейбір Тьюринг машиналары кейбір мәндерінде тоқтамауын байқау қиын емес. Сондықтан, Тьюринг машинасымен есептелетін функцияларды кейде жартылай рекурсивті функция деп атайды, кейде рекурсивті функция деп атайды.

Eнді біз рекурсивті функцияларды қалай нөмірлейтінімізді көрсетейік.

Лемма6.1.Тьюринг машинасының бұйрықтар жиынын нөмірлеп шығуға болады.

Дәлелдеуі.Біз , ,

 

Отправка СМС бесплатно

На правах рекламы


ZERO.kz
 
Модератор сайта RESURS.KZ