Удаан хугацааны өмнө гэж бодъё ... Гэхдээ үнэн хэрэгтээ Тюринг машиныг бүтээхээс өмнө янз бүрийн үйлдэл хийх машинуудыг бүтээсэн. Жишээлбэл, та логарифм, нука авах хэрэгтэй, харин тоог уншиж, логарифм авах машин тавъя. Эсвэл танд хоёр тоо нэмэх хэрэгтэй - энд хоёр тоо нэмэх машин байна. Одоо ч гэсэн ийм машинууд байдаг, жишээлбэл, тооцоолуур. Тэд юу хийж чадах вэ? Нэмэх, хасах, үржүүлэх, инженерчлэх - тэр ч байтугай косинус эсвэл синусыг авна. Эдгээр тэнэг машинууд, тэдгээрт бичигдсэн үйлдлүүдийг эс тооцвол юу ч хийж чадахгүй байсан нь харагдаж байна.

Тиймээс тоо биш, тэмдэг биш харин алгоритмыг уншиж, түүнийгээ гүйцэтгэх програмчлах машин бүтээх ийм машин бүтээх нь маш сонирхолтой байх болно. Энэ бол Тюринг хийсэн зүйл юм (Тюрингээс өөр ийм хийсвэрлэл олон бий гэж би хэлэх болно). Тэгээд тэр ийм машины загвар гаргаж ирэв. Нарийн төвөгтэй алгоритмуудыг хэрэгжүүлэхийн тулд тэрэг, төгсгөлгүй соронзон хальс, соронзон хальс дээр бичигдсэн утгыг өөрчилж, түүний дагуу хөдлөх чадвар л хэрэгтэй болно. Энэхүү хийсвэрлэлийг жинхэнэ машин болгон хувиргаж болох бөгөөд бид машиныг эцэс төгсгөлгүй соронзон хальсаар хангаж чадахгүй гэсэн хязгаарлалттай, гэхдээ бид маш урт соронзон хальс хийх боломжтой болсон.)

Ухрах. Үнэндээ Тюринг машин хэрхэн ажилладаг талаар хэлэх шаардлагагүй, миний хэлсэнчлэн үүнийг маш амархан олж болно. Тиймээс, энэ нь хэрхэн ажилладаг талаар та аль хэдийн мэдэж байсан гэж бид таамаглах болно.

Тьюринг машин нь хэд хэдэн энгийн алгоритмыг гүйцэтгэдэг бөгөөд энэ нь маргаангүй юм. Гэхдээ зальтай хүмүүс яах вэ? Жишээлбэл, MT ашиглан мөчлөгийг хэрхэн зохион байгуулах вэ? Эсвэл салаалалтыг хэрхэн ойлгох вэ? МТ нь гогцоо, мөчир хийж чаддаг гэдгийг нотлох теоремууд байдаг нь маш энгийн механизмаар салбар, гогцоо гэх мэт энгийн блокоос програм зохиох боломжтойг хэлж өгдөг бөгөөд энэ нь програмчилж болох бүх зүйл боломжтой гэсэн үг юм. програмчлагдсан байх. Энд онолын хувьд тооцоолох боломжгүй функцууд байдаг тул шийдвэрлэх боломжгүй асуудлууд байдаг бөгөөд эдгээр асуудлыг MT-ийн тусламжтайгаар шийдвэрлэх боломжгүй гэсэн тайлбар байх ёстой. Хэрхэн яаж хийхийг эндээс үзнэ үү.

Гэхдээ хэн ч Тюринг машинаас өөр гайхалтай зүйлийг зохион бүтээгээгүй тул бидний одоо ашиглаж байгаа бүх програмчлалын хэлүүд нь Тюринг машинаас өөр програмчлах боломжгүй юм. Эндээс Тюринг бүрэн байдлын тухай ойлголт гарч ирсэн бөгөөд энэ нь хэрэв Тюринг машин дээр ажилладаг бүх алгоритмыг бичиж чадвал хэл (эсвэл өөр зүйл) нь Тюринг бүрэн болно гэсэн үг юм. Тюринг машины эмулятор бичих замаар та хэл бүрэн төгс болохыг баталж чадна. Эдгээр нь бялуу юм.

Математикийн үүднээс авч үзвэл шуудан бол тэнэг зүйл боловч Тьюрингийн машин бидэнд юу хэрэгтэй байсан нь ойлгомжтой. Энэ машинд зориулсан алгоритм бичих нь үнэхээр сонирхолтой таавар юм. Тюринг машин дээр exp (x) програмчилсны дараа тэр алгоритм гэж юу болохыг үнэхээр ойлгосон гэж хэлдэг хүмүүс итгэдэг. Одоохондоо туршиж үзээгүй ч сонирхолтой сорилт байна.

Тюринг машин бол дараахь объектуудын цуглуулга юм

• 1) гадаад цагаан толгойн үсэг A = (a 0, a 1,..., a n);
• 2) дотоод цагаан толгойн Q = (q 1, q 2,…, q m) нь төлөв байдлын багц юм;
• 3) хяналтын тэмдэгтүүдийн багц (P, L, S)
• 4) хоёр чиглэлд хязгааргүй соронзон хальс, эс болгон хуваасан бөгөөд тус бүрт нь А цагаан толгойн ганц тэмдэгтийг бичиж болно.
• 5) олон мужид байх боломжтой хяналтын төхөөрөмж

Хоосон нүдний тэмдэг нь цагаан толгойн гаднах a 0 үсэг юм.

Мужийн дунд машин ажиллаж эхлэх анхны q 1 ба машин зогссон эцсийн (эсвэл зогсох төлөв) q 0 -ийг ялгаж үздэг.

Хяналтын төхөөрөмж нь соронзон хальсны дагуу зүүн, баруун тийш хөдөлж, соронзон хальсны нүднүүдэд цагаан толгойн А үсгийг уншиж, бичих боломжтой.Удирдлагын төхөөрөмж нь иймэрхүү харагдах командын дагуу ажилладаг.

q i a j> a p X q k

Оруулга нь дараахь зүйлийг илэрхийлнэ: хэрэв хяналтын төхөөрөмж qi төлөвт байгаа бөгөөд aj үсэг нь ажиглагдсан нүдэнд бичигдсэн бол aj -ийн оронд (1) ap гэж бичнэ, (2) машин дараагийнх руу орно. X = P бол дөнгөж үзсэн баруун нүд, эсвэл X = L бол дараагийн зүүн нүдийг харах эсвэл соронзон хальсны ижил нүдийг үргэлжлүүлэн судлах, X = C бол (3) хяналтын төхөөрөмж төлөвт ордог q k.

Машины ажиллагааг нөхцлөөр нь түүний төлөв байдлаас бүрэн тодорхойлдог тул тухайн мөчид болон тухайн үед нүдний агуулгыг хянаж байдаг тул q i a j боломжит тохиргоо бүрийн хувьд яг нэг дүрэм байдаг. Зөвхөн машин зогсох эцсийн төлөвт зориулсан дүрэм байдаггүй. Иймд гадаад A = (a0, a1,…, an) болон дотоод Q = (q1, q2,…, qm) үсэг бүхий Тьюрингийн машины программ нь хамгийн ихдээ m (n + 1) заавар агуулна.

А үсэг эсвэл Q цагаан толгой эсвэл A Q үсэг дээрх үг бол харгалзах цагаан толгойн үсгийн дараалал юм. k-р тохиргоо гэж бид k-р алхамын эхэнд үүссэн мэдээлэл бүхий машины соронзон хальсны дүрсийг (эсвэл k-ийн эхэнд соронзон хальс дээр бичсэн А цагаан толгойн үгийг) хэлнэ. 3 -р алхам), энэ үе шатанд аль эсийг харж байгааг, машин ямар нөхцөлд байгааг заана. Зөвхөн эцсийн тохиргоо нь утга учиртай, өөрөөр хэлбэл. хязгаарлагдмал тоог эс тооцвол соронзон хальсны бүх эс хоосон байна. Машины байгаа төлөв эцсийн байвал тохиргоог эцсийн гэж нэрлэдэг.

Хэрэв бид Тьюринг машины эцсийн бус тохиргоог анхны хувилбар болгон сонговол машины ажил нь эцсийн тохиргоонд хүрэх хүртэл машины програмын дагуу анхны тохиргоог дараалсан (алхам алхамаар) хийх болно. . Үүний дараа Тьюрингийн машины ажлыг дууссан гэж үзэж, ажлын үр дүн нь хүрсэн эцсийн тохиргоо юм.

A (a 0) = (a 1, ..., an) цагаан толгойн үсгийн хоосон биш b үгийг соронзон хальсны дараалсан нүднүүдэд бичсэн бол стандарт байрлалд байгаа машин хүлээн авдаг гэж бид хэлэх болно. бусад бүх нүд хоосон бөгөөд машин нь b гэсэн үгийг бичсэн хамгийн зүүн эсвэл баруун нүдийг хардаг. Стандарт байрлал дахь үгийг хүлээн авдаг машин нь q 1 анхны төлөвт (тус тусдаа q 0 зогссон төлөвт) байвал стандарт байрлалыг анхны (эцсийн) байрлал гэж нэрлэдэг.

Хэрэв b гэсэн үгийн боловсруулалт нь Тюринг машиныг эцсийн төлөвт шилжүүлбэл энэ нь b -д хамаатай гэж хэлдэг, эс тэгвээс b -д хамаарахгүй (машин тодорхойгүй хугацаагаар ажилладаг)

Жишээ авч үзье:

A = (0, 1) гадаад цагаан толгойтой Тюринг машиныг (энд 0 бол хоосон нүдний тэмдэг юм), дотоод төлөв байдлын цагаан толгой Q = (q 0, q 1, q 2) болон дараах функциональ диаграмтай (хөтөлбөр):

q 1 0> 1 L q 2;

q 1 1> 0 C q 2;

q 2 0> 0 P q 0;

q 2 1> 1 C q 1;

Энэ програмыг хүснэгт ашиглан бичиж болно

Эхний алхамд дараах тушаал ажиллана: q 1 0> 1 Л q 2 (хяналтын төхөөрөмж q1 төлөвт байгаа бөгөөд ажиглагдсан нүдэнд 0 үсэг, нүдэнд 0-ийн оронд 1, толгой зүүн тийш шилжиж, хяналтын төхөөрөмж q2 төлөвт орно), үүний үр дүнд машин дээр дараахь тохиргоог бий болгоно.

Эцэст нь q 2 0> 0 P q 0 командыг ажиллуулсны дараа тохиргоо хийгдэнэ

Энэ тохиргоо нь эцсийнх юм, учир нь машин q 0 зогсох байдалд байсан.

Тиймээс 110 гэсэн эх үгийг машин боловсруулж 101 үг болгон хувиргадаг.

Үүсгэсэн тохиргооны дарааллыг илүү богино хэлбэрээр бичиж болно (ажиглагдсан нүдний агуулгыг тухайн машин одоо байгаа улсын баруун талд бичсэн болно):

11q 1 0 => 1 q 2 11 => 1q 1 11 => 1q 2 01 => 10q 0 1

Тюринг машин бол A Q цагаан толгойн үсгийг өөрчлөх дүрэм (алгоритм) -аас өөр зүйл биш юм. тохиргоо. Тиймээс Тьюринг машиныг тодорхойлохын тулд та түүний гадаад болон дотоод цагаан толгойн програмыг зааж өгөх ёстой бөгөөд аль тэмдэгт нь хоосон нүд болон эцсийн төлөвийг илэрхийлж байгааг зааж өгөх хэрэгтэй.

Тьюрингийн машин бол 20-р зууны хамгийн сонирхолтой, сэтгэл хөдөлгөм оюуны нээлтүүдийн нэг юм. Энэ бол компьютерийн аливаа ажлыг хэрэгжүүлэхэд хангалттай ерөнхий бөгөөд тооцооллын (компьютер ба дижитал) энгийн бөгөөд ашигтай хийсвэр загвар юм. Энгийн тайлбар, математик шинжилгээний ачаар компьютерийн шинжлэх ухааны онолын үндэс суурийг бүрдүүлжээ. Энэхүү судалгаа нь дижитал компьютер, тооцооллын талаар илүү гүнзгий ойлголттой болоход хүргэсэн бөгөөд үүнд энгийн хэрэглэгчийн компьютер дээр шийдвэрлэх боломжгүй зарим тооцооллын асуудлууд байдгийг ойлгоход хүргэсэн.

Алан Тьюринг компьютер шиг үндсэн чадвартай механик төхөөрөмжийн хамгийн анхны загварыг тайлбарлахыг зорьсон. Тюринг 1936 онд Лондонгийн Математикийн Нийгэмлэгийн Proceedings сэтгүүлд гарсан "Шийдэгдэхүүний хэрэглээг ашиглан тооцоолох боломжтой тоонуудын тухай" нийтлэлдээ уг машиныг анх дүрсэлсэн байдаг.

Тьюринг машин бол унших / бичих толгой (эсвэл "сканнер") -аас бүрдсэн, цаасан соронзон хальс бүхий тооцоолох төхөөрөмж юм. Тууз нь квадратуудад хуваагддаг бөгөөд тус бүр нь "0" эсвэл "1" гэсэн нэг тэмдэгтийг агуулдаг. Механизмын зорилго нь энэ нь орох, гарах хэрэгсэл, тооцооллын завсрын үе шатуудын үр дүнг хадгалах ажлын санах ойн үүрэг гүйцэтгэдэг. Төхөөрөмж нь юунаас бүрддэг вэ Ийм машин бүр нь хоёр бүрэлдэхүүн хэсгээс бүрдэнэ: Хязгааргүй соронзон хальс. Энэ нь хоёр чиглэлд хязгааргүй бөгөөд эсүүдэд хуваагддаг. Автомат машинаар удирддаг програм, өгөгдлийг унших, бичих толгой сканнер. Энэ нь олон муж улсын аль нэгэнд ямар ч үед байж болно.

Машин бүр хоёр хязгаарлагдмал эгнээний өгөгдлийг холбодог: орж ирж буй тэмдэгтийн цагаан толгой A = (a0, a1, ..., am) ба Q = (q0, q1, ..., qp) мужуудын цагаан толгой. Q0 төлөвийг идэвхгүй гэж нэрлэдэг. Төхөөрөмжийг цохиход түүний ажил дуусдаг гэж үздэг. Q1 төлөвийг анхны төлөв гэж нэрлэдэг - машин нь эхнээс нь тооцоолж эхэлдэг. Оруулах үг нь соронзон хальс дээр байрладаг бөгөөд байрлал бүрт нэг үсэг дараалан байрлана. Түүний хоёр талд зөвхөн хоосон эсүүд байрладаг.

Механизм хэрхэн ажилладаг талаар

Тьюринг машин нь тооцоолох төхөөрөмжөөс үндсэн ялгаа байдаг - санах ойн төхөөрөмж нь төгсгөлгүй соронзон хальстай бол дижитал төхөөрөмжид ийм төхөөрөмж нь тодорхой урттай туузтай байдаг. Даалгаврын анги бүрийг зөвхөн нэг барьсан Тьюринг машин шийддэг. Өөр төрлийн асуудлууд нь шинэ алгоритм бичихтэй холбоотой байдаг. Хяналтын төхөөрөмж нь нэг төлөвт байгаа тул туузны дагуу аль ч чиглэлд хөдөлж чаддаг. Энэ нь эсүүдэд бичиж, эцсийн цагаан толгойн тэмдэгтүүдийг тэднээс уншдаг. Хөдөлгөөний явцад оролтын өгөгдөл агуулаагүй байрлалыг бөглөх хоосон элементийг сонгоно. Тюринг машины алгоритм нь хяналтын төхөөрөмжийн шилжилтийн дүрмийг тодорхойлдог. Тэд унших-бичих толгойд дараах параметрүүдийг тавьдаг: нүдэнд шинэ тэмдэгт бичих, шинэ төлөвт шилжих, соронзон хальсны дагуу зүүн эсвэл баруун тийш шилжих.

Механизмын шинж чанар

Тьюрингийн машин нь бусад тооцоолох системүүдийн нэгэн адил өөрийн онцлог шинж чанартай бөгөөд тэдгээр нь алгоритмын шинж чанаруудтай төстэй: Discreteness. Дижитал машин өмнөх алхамаа хийж дууссаны дараа л дараагийн алхам n + 1 рүү орно. Дууссан үе шат бүр n + 1 гэж юу болохыг тодорхойлдог. Ойлгомжтой байдал. Төхөөрөмж нь нэг нүдэнд зөвхөн нэг үйлдэл хийдэг. Энэ нь цагаан толгойн тэмдэгтийг бичээд нэг хөдөлгөөн хийдэг: зүүн эсвэл баруун. Детерминизм. Механизм дахь байрлал бүр нь тухайн схемийг гүйцэтгэх ганц сонголттой нийцдэг бөгөөд үе шат бүрт түүний үйлдэл, дараалал нь хоёрдмол утгагүй байдаг. Үр дүнтэй байдал. Шат бүрийн тодорхой үр дүнг Тьюрингийн машинаар тодорхойлно. Хөтөлбөр нь алгоритмыг гүйцэтгэдэг бөгөөд хязгаарлагдмал тооны алхмаар q0 төлөвт шилждэг. Массын дүр. Төхөөрөмж бүрийг зөв цагаан толгойн үсгээр тодорхойлсон болно. Тюринг машины функцууд Алгоритмуудыг шийдвэрлэхэд ихэвчлэн функцийг хэрэгжүүлэх шаардлагатай болдог. Тооцоолохын тулд гинжийг бичих боломжоос хамааран функцийг алгоритмын дагуу шийдэгдэх эсвэл шийдвэрлэх боломжгүй гэж нэрлэдэг. Натурал эсвэл рационал тоонуудын хувьд, машинд зориулагдсан N үсэг бүхий хязгаарлагдмал цагаан толгойн үсгийн хувьд бид B = (0.1) хоёртын кодын цагаан толгойн хүрээнд орсон олонлогийн дарааллыг авч үздэг. Мөн тооцооллын үр дүнд алгоритм "дүүжлэх" үед тохиолддог "тодорхойгүй" утгыг харгалзан үздэг. Функцийг хэрэгжүүлэхийн тулд албан ёсны хэл нь хязгаарлагдмал цагаан толгойд байх ёстой бөгөөд зөв тайлбарыг таних асуудал шийдэгдэх нь чухал юм.

Төхөөрөмжийн програм

Тюринг механизмын програмууд нь эхний мөр, баганад гадаад цагаан толгойн тэмдэг, автомат дотоод дотоод төлөв байдлын утгыг агуулсан хүснэгт хэлбэрээр форматлагдсан болно. Хүснэгтийн өгөгдөл нь Тьюрингийн машинд мэдрэгддэг тушаалууд юм. Асуудлын шийдэл дараах байдалтай байна: одоогоор байрлаж байгаа нүдэн дэх толгойн уншсан үсэг, машины толгойн дотоод байдал нь аль командыг гүйцэтгэх ёстойг тодорхойлдог. Тодруулбал, ийм тушаал нь хүснэгтэд байгаа гадаад болон дотоод цагаан толгойн тэмдгийн уулзвар дээр байрладаг.

Тооцооллын бүрэлдэхүүн хэсгүүд

Тодорхой нэг асуудлыг шийдэх Тьюринг машин бүтээхийн тулд дараах параметрүүдийг тодорхойлох шаардлагатай. Гадаад цагаан толгой. Энэ бол А тэмдгээр тэмдэглэгдсэн, элементүүдийг үсгээр нэрлэсэн зарим хязгаарлагдмал тэмдэг юм. Тэдний нэг нь - a0 - хоосон байх ёстой. Жишээлбэл, хоёртын тоон дээр ажилладаг Тьюринг төхөөрөмжийн цагаан толгой иймэрхүү харагдаж байна: A = (0, 1, a0). Туузан дээр бичигдсэн үсгийн тэмдгийн тасардаггүй мөрийг үг гэж нэрлэдэг. Автомат бол хүний ​​оролцоогүйгээр ажилладаг төхөөрөмж юм. Тьюринг машинд энэ нь асуудлыг шийдвэрлэх хэд хэдэн өөр төлөвтэй бөгөөд тодорхой нөхцөлд нэг байрлалаас нөгөө байрлал руу шилждэг. Ийм тэрэгний төлөвүүдийн цуглуулга нь дотоод цагаан толгой юм. Түүнд байгаа үсэгний тэмдэглэгээ Q = (q1, q2 ...) хэлбэрийн. Эдгээр байрлалуудын нэг нь - q1 - эхнийх нь байх ёстой, өөрөөр хэлбэл програмыг эхлүүлдэг зүйл байх ёстой. Өөр нэг шаардлагатай элемент бол q0 төлөв бөгөөд энэ нь эцсийнх юм, өөрөөр хэлбэл програмыг цуцалж, төхөөрөмжийг зогсоолын байдалд хүргэдэг.

Үсрэх ширээ.

Энэ бүрэлдэхүүн хэсэг нь тухайн машины төлөв байдал, уншиж буй тэмдэгтийн үнэ цэнээс хамааран төхөөрөмжийн тэрэгний зан үйлийн алгоритм юм.

Автомат төхөөрөмжийн алгоритм

Ашиглалтын явцад Тюринг төхөөрөмжийг тээвэрлэх ажлыг алхам тутамд дараах дарааллаар гүйцэтгэдэг програмаар хянадаг: Гадаад цагаан толгойн тэмдэгтийг хоосон байрлалд оруулах, түүний дотор байгаа элементийг орлуулах, хоосон оруулах. Нэг нүдийг зүүн эсвэл баруун тийш шилжүүл. Таны дотоод байдлыг өөрчлөх. Тиймээс, хос тэмдэгт эсвэл байрлал бүрт програм бичихдээ гурван параметрийг нарийн тодорхойлох шаардлагатай: ai - сонгосон цагаан толгойн A элемент, тэрэгний шилжих чиглэл ("←" зүүн тийш, "→" баруун, "цэг" - хөдөлгөөн байхгүй) болон qk - төхөөрөмжийн шинэ төлөв Жишээ нь, "←" q2 тушаал 1 "тэмдэгтийг 1-ээр сольж, тэрэгний толгойг зүүн тийш нэг нүдний алхам руу шилжүүлж, төлөвт шилжих q2 ".

Бид ихэвчлэн янз бүрийн нарийн төвөгтэй асуудлыг шийддэг: өдөр тутмын, математик гэх мэт. Заримыг нь шийдэхэд амархан, заримыг нь маш их бодох хэрэгтэй, заримд нь хэзээ ч шийддэггүй.

Ерөнхий тохиолдолд асуудлыг шийдвэрлэх арга замыг (хэрэв байгаа бол) хязгаарлагдмал тооны энгийн үйлдлүүдийг ашиглан дүрсэлж болно.

Жишээлбэл, квадрат тэгшитгэлийг шийдэхийн тулд:

1. Тэгшитгэлийг каноник хэлбэрт аваач \ (a x ^ 2 + b x + c = 0 \)
2. Хэрэв \ (a = 0 \) бол энэ нь шугаман тэгшитгэлуусмалаар \ (x = \ frac (-c) (b) \). Асуудлыг шийдсэн. Үгүй бол 3-р алхам руу очно уу.
3. Ялгаварлан гадуурхагчийг тооцоолох \ (D = b ^ 2-4 a c \)
4. Тэгшитгэлийн шийдлүүдийг тооцоол \ (x_ (1,2) = \ frac (-b \ pm \ sqrt (D)) (2 a) \)... Асуудлыг шийдсэн.

Та алгоритмын дараах зөн совингийн ойлголтыг танилцуулж болно.

Алгоритм гэдэг нь аливаа өгөгдлийн анхны багцад хязгаарлагдмал тооны үйлдлээр асуудлыг шийдвэрлэх үр дүнд хүрэхийн тулд гүйцэтгэгчийн үйл ажиллагааны дарааллыг тодорхойлсон зааварчилгааны багц юм.

Мэдээжийн хэрэг, энэ бол хатуу тодорхойлолт биш боловч алгоритмын үзэл баримтлалын мөн чанарыг тайлбарласан болно.

Алгоритмыг тодорхой зүйл дээр үндэслэн боловсруулдаг гүйцэтгэгч, үүний дагуу гүйцэтгэгчийн ойлгодог хэлээр боловсруулсан байх ёстой.

Алгоритмын гүйцэтгэгч нь хүн байж болно, эсвэл энэ нь компьютер эсвэл бусад машин байж болно, жишээлбэл, нэхэх машин.

Алгоритмуудын дараах шинж чанаруудыг онцлон тэмдэглэв.

Алгоритмын салангид байдал нь тусдаа, тодорхой тодорхойлогдсон алхам (үйлдэл) -ийн тодорхой дараалал байх ёстой. Эдгээр үйлдэл бүр цаг хугацааны хувьд хязгаарлагдмал байх ёстой. Алгоритмын алхам бүрт детерминизм, дараагийн алхам нь системийн өнөөгийн байдлаас өвөрмөц байдлаар тодорхойлогддог. Үүний үр дүнд, ижил өгөгдөл дээр алгоритм нь хичнээн олон удаа хийгдсэнээс үл хамааран үргэлж ижил үр дүнг өгдөг. Ойлгомжтой байдал Алгоритмыг гүйцэтгэгчид ойлгомжтой хэлээр томъёолсон байх ёстой. Хэрэв ирдэгкомпьютер дээр алгоритм нь зөвхөн компьютерт мэдэгдэж байгаа бөгөөд үр дүнг нь нарийн тодорхойлсон тушаалуудыг ашиглах ёстой. Алгоритмын төгсгөлийг хэд хэдэн алхамаар дуусгах ёстой. Алгоритмын масс нь янз бүрийн оролтын өгөгдлийн багцад хамаарах ёстой. Өөрөөр хэлбэл алгоритм нь шийдвэрлэхэд тохиромжтой байх ёстой ангидаалгавар. Квадрат жишээ рүү буцаж ирэхэд алгоритм нь шийдвэрлэхэд тохиромжтой бүгдквадрат тэгшитгэл, зөвхөн нэг ба түүнээс дээш биш. Алгоритмын үр нөлөө нь тодорхой үр дүнгээр дуусах ёстой. Асуудлыг шийдэх эсвэл шийдэл байхгүй гэдгийг олж мэдэх замаар хэлээрэй. Хэрэв алгоритм нь үр дүнд хүргэхгүй бол яагаад хэрэгтэй байгаа нь тодорхойгүй байна.

Асуудлыг шийдэх бүх арга нь алгоритм биш юм. Алгоритм нь ямар ч сонголтгүй гэсэн үг юм. Жишээлбэл, ихэнх нь хоолны жорТэд "амтлахын тулд давс нэмнэ" гэх мэт хэллэг ашигладаг тул алгоритм биш юм. Үүний үр дүнд детерминизмын шаардлага зөрчигдөж байна.

Шийдэл байгаа асуудал болгонд шийдлийн алгоритм бас байдаг. Жишээлбэл, дүрсийг таних асуудал нэлээд шийдэгдээгүй байгаа бөгөөд хатуу алгоритм ашиглаагүй байна. Гэсэн хэдий ч мэдрэлийн сүлжээг ашиглах нь маш сайн үр дүнг өгдөг.

Ихэвчлэн алгоритмын багцууд байдаг зөвшөөрөгдсөнмэдээлэл оруулах. Тэгшитгэлийн алгоритмыг оройн хоол хийхдээ ашиглахыг оролдох нь хачирхалтай байх болно.

Нэмж дурдахад, жүжигчний хийх боломжтой үйл ажиллагааны багц хязгаарлагдмал байдаг, учир нь хэрэв ямар нэгэн үйлдэл хийхийг зөвшөөрсөн бол тэдний дунд "хүлээн зөвшөөрөгдөхгүй" байх ёстой.

Алгоритмын хатуу тодорхойлолт

Дээрх алгоритмын тодорхойлолт нь хатуу биш юм. Энэ нь зарим хүндрэлийг бий болгодог. Тодруулбал, ийм тодорхойлолтоор тухайн ангиллын асуудлыг алгоритмаар шийдвэрлэх боломжтой эсэхийг баттай нотлох боломжгүй юм.

Анги байгаа нь харагдаж байна алгоритмын хувьд шийдэгдээгүй асуудлууд- шийдлийн алгоритм зохиох боломжгүй асуудлууд. Гэхдээ алгоритмын шийдвэр гаргах боломжгүй гэдгийг хатуу нотлохын тулд та эхлээд алгоритмын нарийн тодорхойлолттой байх хэрэгтэй.

XX зууны 20-30-аад оны үед янз бүрийн математикчид алгоритмын хатуу тодорхойлолтын асуудал дээр ажиллаж байсан, тухайлбал Алан Тюринг, Эмил Леон Пост, Андрей Андреевич Марков, Андрей Николаевич Колмогоров, Алонзо сүм болон бусад хүмүүс. Тэдний ажил эцэст нь алгоритмын онол, тооцооллын онол, тооцооллын янз бүрийн хандлага, мөн ерөнхийдөө програмчлалыг бий болгож, хөгжүүлэхэд хүргэсэн. Тэдний ажлын үр дүнгийн нэг нь алгоритмын янз бүрийн хэлбэрээр танилцуулсан боловч хоорондоо дүйцэхүйц хэд хэдэн тодорхойлолтууд гарч ирсэн явдал юм.

Бид Тюрингын тодорхойлолтын талаар нарийвчлан ярилцаж, Пост, Сүм, Марковын ижил төстэй тодорхойлолтуудад өнгөц дүн шинжилгээ хийх болно.

Тюринг хийх машин

Алгоритмын албан ёсны тодорхойлолтыг танилцуулахын тулд Тьюринг Тюринг тооцоолох машин, эсвэл зүгээр л Тюринг машин гэж нэрлэгддэг хийсвэр тооцоолох машиныг гаргаж ирэн тайлбарлав.

Алан Тюринг (1912-1954)

Английн математикч, логикч, криптографч, магадгүй дэлхийн анхны “хакер” компьютерийн шинжлэх ухаан, хиймэл оюун ухааны онолын тэргүүн эгнээнд байсан. Тэрээр Дэлхийн 2 -р дайнд холбоотнуудын хүчийг ялахад чухал хувь нэмэр оруулсан.

Тюринг машины оролтын өгөгдөл нь үгтодорхой тусламжтайгаар эмхэтгэсэн цагаан толгой, өөрөөр хэлбэл багц тэмдэгтүүд.

Тюринг машины ажлын үр дүн бол үг юм.

Алгоритмыг ашигладаг үгийг дууддаг оролт... Ажлаас гаралтай үг амралтын өдөр.

Алгоритмыг ашигладаг үгсийн багцыг нэрлэдэг алгоритмын хамрах хүрээ.

Хатуухан хэлэхэд аливаа объектыг цагаан толгойн үсгээр бичсэн үг хэлбэрээр дүрслэх боломжтой гэдгийг батлах боломжгүй юм - үүний тулд бидэнд тухайн объектын нарийн тодорхойлолт хэрэгтэй болно. Гэсэн хэдий ч объект дээр ажилладаг аливаа санамсаргүй алгоритмыг хувиргаж, алгоритмын мөн чанарыг өөрчлөхгүйгээр үг дээр ажиллах боломжтой эсэхийг шалгаж болно.

Тюринг машины тодорхойлолт

Тьюринг машин нь хоёр чиглэлд хязгааргүй соронзон хальс, эсүүдэд хуваагдсан, хяналтын төхөөрөмж (үүнийг бас нэрлэдэг унших-бичих толгой, эсвэл зүгээр л машин), олон муж улсын аль нэгэнд байх чадвартай. Хяналтын төхөөрөмжийн боломжит төлөвүүдийн тоо нь хязгаарлагдмал бөгөөд нарийн тодорхойлогдсон байдаг.

Хяналтын төхөөрөмж нь соронзон хальсны дагуу зүүн, баруун тийш шилжих, хязгаарлагдмал цагаан толгойн тэмдэгтүүдийг нүд рүү унших, бичих боломжтой. \ (A_0 \) эсвэл \ (\ Lambda \) гэж тэмдэглэсэн тусгай хоосон тэмдэгтийг хуваарилсан бөгөөд энэ нь оролтын өгөгдлийг бичсэн соронзон хальснаас бусад бүх нүдийг дүүргэдэг.

Хянагч нь тухайн Тюринг машинаар хэрэгжүүлсэн алгоритмыг илэрхийлсэн шилжилтийн дүрмийн дагуу ажилладаг. Шилжилтийн дүрэм бүр нь тухайн машины одоогийн төлөв болон тухайн нүдэнд ажиглагдсан тэмдгээс хамаарч энэ нүдэнд шинэ тэмдэг бичиж, шинэ төлөвт шилжиж, нэг нүдийг зүүн эсвэл баруун тийш шилжүүлэхийг зааварчилдаг. Тюринг машины зарим төлөвийг терминал гэж тэмдэглэж болох бөгөөд тэдгээрийн аль нэг рүү шилжих нь ажлын төгсгөл, алгоритмыг зогсоох гэсэн үг юм.

Хэдийгээр Тьюрингийн машин нь хийсвэр ойлголт боловч ийм машиныг төсөөлөхөд л хангалттай (хязгаарлагдмал соронзон хальстай ч гэсэн), үүнтэй төстэй демо машинууд ч байдаг.

Тьюрингийн машины алгоритмыг хүснэгт хэлбэрээр илэрхийлэх нь тохиромжтой: хүснэгтийн баганууд нь соронзон хальс дээрх одоогийн (ажиглагдсан) тэмдэгтэй, мөрүүд нь машины одоогийн төлөвтэй тохирч, нүднүүд нь машин гүйцэтгэх команд.

Тушаал нь дараахь бүтэцтэй байж болно.

\ [a_k \ зүүн \ lbrace \ эхлэх (матриц) L \\ N \\ R \ төгсгөл (матриц) \ баруун \ rbrace q_m \]

Эхлээд цагаан толгойн тэмдэг гарч ирэх бөгөөд үүнийг \ (a_k \) нүдэнд бичих ёстой бөгөөд дараа нь машины хөдөлгөөнийг зүүн тийш (L), баруун тийш (P) эсвэл хаана ч (байрандаа бай, H) зааж өгнө. . Төгсгөлд нь \ (q_m \) автомат машин орох ёстой шинэ төлөвийг зааж өгсөн болно.

Хүснэгтийн нүдийг одоогийн тэмдэгт \ (a_i \) болон машины одоогийн төлөв \ (q_j \) тодорхой тодорхойлсон болно.

Ажлын эхэнд Тьюрингийн машин байгаа гэдэгтэй санал нийлэе анхны төлөв, \ (q_1 \) гэж тэмдэглэсэн бөгөөд шилжих үед байдлыг зогсоо\ (q_0 \) алгоритм дуусч, машин зогсох болно.

Жишээ

Тюринг машины алгоритмыг зохиогоод оролтын үгэнд нэмэх болно аравтын тоо, 1.

Дараа нь алгоритмыг тайлбарлахдаа дараах байдлаар томъёолж болно.

1. Баруун тийш шилжихдээ оролтын үгийн эхлэлийг олоорой
2. Баруун тийш шилжихдээ оролтын үгийн төгсгөлийг олоорой
3. Оруулсан үгийн одоогийн бит дээр нэгийг нэмнэ үү. Хэрэв 0 -ээс 8 хүртэл тоо байгаа бол гарна уу. Үгүй бол 0 гэж бичээд зүүн тийш хөдөлж, 3 -р алхам руу буцна уу.

Энэ алгоритмыг хүснэгт хэлбэрээр бичье. Цагаан толгой нь 0 -ээс 9 хүртэлх тоонууд ба хоосон тэмдэгтээс бүрдэнэ \ (\ Lambda \). Алгоритмын тайлбар дахь алхамуудтай тохирч зогсох төлөвийг тоолж үзэхэд автомат 4 төлөв хэрэгтэй болно.

Анхны төлөв \ (1 \) нь оролтын үгийн эхлэл, \ (2 \) нь оролтын үгийн төгсгөл, \ (3 \) нь 1 -ийн нэмэгдэл гэдгийг хүлээн зөвшөөрцгөөе.

\ (_ (q_j) \ арын ташуу ^ (a_i) \)	Λ	0	1	2	3	4	5	6	7	8	9
1	1П1	0H2	1Н2	2H2	3H2	4Н2	5H2	6H2	7H2	8H2	9H2
2	3Л3	0P2	1P2	2P2	3P2	4P2	5P2	6P2	7P2	8P2	9P2
3	1H0	1H0	2H0	3H0	4H0	5H0	6H0	7H0	8H0	9H0	0L3

Энэ алгоритмын үйл ажиллагааг жишээгээр харцгаая. Эхний мөр нь соронзон хальсны харгалзана, хоёр дахь нь машины байрлал, түүний одоогийн байдлыг заана.

	1	9	9
1

1 -р төлөвт автомат машин нь хоосон нүдний дээгүүр байна. "ΛП1" хүснэгтийн харгалзах команд, өөрөөр хэлбэл нүдийг хоосон орхиж, баруун тийш шилжиж 1 төлөвт байгаарай.

	1	9	9
	1

Одоо автомат машин "1" утгыг хянаж байна. "1H2" гэсэн харгалзах команд, өөрөөр хэлбэл нүдэнд "1" үлдээж, хөдөлж болохгүй, "2" төлөвт орно уу.

	1	9	9
	2

"2" төлөвт машин нь "1" утгыг ажигладаг. "1P2" гэсэн харгалзах тушаал, өөрөөр хэлбэл "1" -ийг орхиж, баруун тийш шилжиж "2" төлөвт байгаарай.

Нөхцөл байдал давтагдана:

Одоо 3 -р төлөвт "9" тэмдгийг ажиглаж, машин "0L3" командыг гүйцэтгэдэг.

	1	9	0
		3

Нөхцөл байдал давтагдана:

"0" төлөв - зогсолтын төлөв. Алгоритм дууссан.

Албан ёсны тодорхойлолт

Математикийн хувьд Тюринг машиныг дараах байдлаар дүрсэлж болно.

Тюринг машин (MT)

энэ бол хэлбэрийн систем юм \ (\ (A, a_0, Q, q_1, q_0, T, \ tau \) \), хаана

• \ (A \) - MT цагаан толгойн тэмдэгтүүдийн хязгаарлагдмал багц
• \ (a_0 \ A \) - цагаан толгойн хоосон тэмдэгт
• \ (Q \) нь MT -ийн хязгаарлагдмал төлөвүүдийн багц юм
• \ (Q_1 \ Q \ -д) - MT -ийн анхны төлөв
• \ (Q \ дахь q_0 \) - MT-ийн эцсийн төлөв (зогсоох төлөв)
• \ (T = \ (A, P, H \) \) нь MT ээлжийн багц юм
• \ (\ tau \) - MT програм, өөрөөр хэлбэл зураглалыг тодорхойлдог функц \ (\ tau: A \ times Q \ backslash \ (q_0 \) \ rightarrow A \ times T \ times Q \)

Алгоритмын онолын түлхүүр нь юм Тюрингын диссертаци.

Тюрингын диссертацийг сул хэллэгээр дараах байдлаар томъёолсон болно.

Алгоритмоор шийдэгдэх аливаа асуудалд зориулсан Тьюрингийн диссертацид энэ асуудлыг шийддэг Тьюрингийн машин байдаг. Үгүй бол аливаа алгоритмын хувьд түүнтэй адилтгах Тьюринг машин байдаг.

Тюрингын диссертаци нь алгоритмын талаар нэлээд энгийн математик аппарат ашиглан ярих боломжийг бидэнд олгодог. Түүгээр ч барахгүй Тьюрингийн машин өөрөө бүх нийтийн идэвхжүүлэгч, ийм төсөөллийн машин бүтээх боломж нь бүх нийтийн тооцоолох технологийг бий болгох тухай ярих шалтгаан болсон юм.

Алгоритмын өөр хувилбаруудын тодорхойлолт

Тьюринг машинаас гадна хэд хэдэн бие даасан тодорхойлолтууд байдаг.

Тодруулбал, шуудангийн машинаар дамжуулан, Сүмийн ламбда тооцооллын тусламжтайгаар Марковын ердийн алгоритм.

Эдгээр аргуудыг авч үзье.

Шуудангийн машин

Тюрингээс нэг жилийн дараа Америкийн математикч Эмил Леон Пост өөр нэг хийсвэр бүх нийтийн тооцоолох машиныг бие даан санал болгов.

Шуудангийн машин нь хоёр оронтой цагаан толгойн үсгээр ажилладаг бөгөөд машины дотоод төлөв байдлыг орлуулдаг програмын шугам.

Үгүй бол шуудангийн машин нь Тьюринг машинтай төстэй: автомат машин байдаг, эсүүдтэй төгсгөлгүй соронзон хальс байдаг.

Шуудангийн машин нь дараах тушаалуудыг гүйцэтгэх боломжтой.

1. 1 гэж бичээд програмын i-р мөрөнд орно
2. 0 гэж бичээд програмын i-р мөр рүү очно уу
3. Зүүн тийш шилжиж, програмын i-р мөр рүү очно уу
4. Баруун тийш шилжиж, програмын i-р мөр рүү очно уу
5. Нөхцөлт үсрэлт: хэрэв ажиглагдсан нүдэнд 0 байвал програмын i-р мөр рүү, эс бөгөөс програмын j-р мөр рүү очно уу.
6. Зогс.

Шуудангийн машин нь хэд хэдэн хориотой тушаалуудтай:

1. Аль хэдийн 1 байгаа үед 1-р нүд рүү бичих.
2. Аль хэдийн 0 байгаа үед 0 нүд рүү бичих.

Ийм үйл явдал нь сүйрэлд хүргэдэг.

Шуудангийн машинд програм бичихийн тулд та дараах тэмдэглэгээг ашиглаж болно.

1. ∨ i - 1 гэж бичээд програмын i-р мөрөнд очно
2. × i - 0 гэж бичээд програмын i -р мөр рүү очно уу
3. ← i - зүүн ээлжийг хийж, програмын i -р мөр рүү очно уу
4. → i - баруун тийш шилжиж, програмын i -р мөр рүү очно уу
5. ? би; j - нөхцөлт үсрэлт: Хэрэв ажиглагдсан нүдэнд 0 байвал програмын i-р мөрөнд, үгүй ​​бол програмын j-р мөрөнд очно.
6. ! - Зогс.

Хөтөлбөрийн жишээ:

1. → 2 2.? 1; 3 3. × 4 4. ← 5 5.!

Энэ програм нь машины эхлэх байрлалын баруун талд байрлах эхний шошгыг (1) устгаж, машиныг зүүн талын нүдэнд зогсооно.

Ерөнхийдөө Post-ын машин бол өмнөх загвар юм зайлшгүйпрограмчлалын хэл, жишээ нь C, Fortran гэх мэт.

Шуудангийн машин нь Тьюрингийн машинтай тэнцэнэ. Өөрөөр хэлбэл, Тьюринг машинд зориулсан аливаа програмын хувьд та Post машинтай дүйцэх програм бичиж болно, мөн эсрэгээр.

Энэ тэгшитгэлийн нэг чухал үр дагавар нь Аливаа цагаан толгойг хоёртын код болгон бууруулж болно.

Тюрингын диссертацийн нэгэн адил Постын дипломын ажил бас байдаг.

Шуудангийн диссертацийг аливаа алгоритмыг шуудангийн машин хэлбэрээр дүрсэлж болно.

Ердийн Марков алгоритм

Марковын ердийн алгоритмууд нь янз бүрийн цагаан толгойн үсгээр хэрэглэгддэг.

Аливаа ердийн алгоритмын тодорхойлолт нь хоёр хэсгээс бүрдэнэ.

1. Цагаан толгойалгоритм
2. Схемалгоритм

Алгоритмыг өөрөө ашигладаг үгс, өөрөөр хэлбэл дүрүүдийн дараалал цагаан толгой.

Ердийн алгоритмын схемийг төгсгөлтэй эрэмбэлэгдсэн олонлог гэж нэрлэдэг орлуулах томъёо, тус бүр байж болно энгийнэсвэл финал... \ (L \ to D \) хэлбэрийн илэрхийлэлийг энгийн орлуулах томъёо гэж нэрлэдэг бөгөөд энд \ (L \) ба \ (D \) нь алгоритмын цагаан толгойноос бүрдсэн хоёр дурын үг бөгөөд үүнийг зүүн ба баруун гэж нэрлэдэг. орлуулах томъёоны талууд). Үүнтэй адилаар орлуулах эцсийн томъёо нь \ (L \ to \ cdot D \) хэлбэрийн илэрхийлэл бөгөөд \ (L \) ба \ (D \) нь алгоритмын цагаан толгойн үсгээс бүрдсэн хоёр дурын үг юм.

\ (\ To \) ба \ (\ to \ cdot \) туслах тэмдэгтүүд нь алгоритмын цагаан толгойд хамаарахгүй гэж үздэг.

\ (V \) дурын үгэнд ердийн алгоритмыг хэрэглэх үйл явц нь дараах үйлдлийн дараалал юм.

1. \ (V "\) нь алгоритмын өмнөх шатанд олж авсан үг (эсвэл одоогийн алхам эхнийх бол анхны үг) байг.
2. Хэрэв орлуулах томъёонуудын дунд орлуулалт байхгүй бол зүүн тал нь \ (V "\" -д багтах болно), алгоритмын ажлыг бүрэн гүйцэд гэж үзэх бөгөөд энэ ажлын үр дүн нь \ (V" \ гэсэн үг юм. ).
3. Үгүй бол зүүн тал нь \ (V "\) -д багтсан орлуулах томъёонуудаас хамгийн эхнийх нь сонгогдоно.
4. \ (V "\) үгийн \ (RLS \) (энд \ (R \) нь угтвар, \ (L \) нь дагавар) хэлбэрийн бүх боломжит дүрслэлүүдээс нэгийг нь сонгосон болно. (R \) нь хамгийн богино нь орлуулалт юм \ (V "= RDS \).
5. Хэрэв орлуулах томъёо хязгаартай байсан бол алгоритмыг \ (V "\) үр дүнгээр бөглөнө. Үгүй бол 1 -р алхам руу (дараагийн алхам) орно.

Аливаа ердийн алгоритм нь зарим Тьюринг машинтай тэнцэх бөгөөд эсрэгээрээ аливаа Тюринг машин нь ердийн алгоритмтай тэнцдэг.

Ердийн алгоритмын талаархи Тюрингын диссертацийн аналогийг ихэвчлэн нэрлэдэг хэвийн болгох зарчим.

Жишээ

Энэ алгоритм нь хоёртын тоог “нэг” болгон хувиргадаг (үүнд сөрөг бус бүхэл тооны N бичлэг нь N тэмдэгтийн мөр юм). Жишээлбэл, 101 хоёртын тоог 5 саваа болгон хөрвүүлдэг: |||||

Цагаан толгой: (0, 1, |) Дүрэм:

1. 1 → 0|
2. |0 → 0||
3. 0 -> (хоосон мөр)

Эх мөр: 101 Гүйцэтгэл:

1. 0|00|
2. 00||0|
3. 00|0|||
4. 000|||||
5. 00|||||
6. 0|||||
7. |||||

Рекурсив функцууд

Тюринг машинтай дүйцэхүйц системийг математикийн функц дээр үндэслэн бүтээж болно. Үүний тулд бид дараах функцүүдийн ангиллыг нэвтрүүлэх хэрэгтэй.

• анхдагч рекурсив функцууд
• ерөнхий рекурсив функцууд
• хэсэгчлэн рекурсив функцууд

Сүүлчийн анги нь Тьюрингийн тооцоолдог функцуудын ангилалтай давхцах болно (өөрөөр хэлбэл Тьюрингийн машинд зориулсан алгоритмыг үүсгэж болох тооцоолох функцууд).

Рекурсив функцээр дамжуулан алгоритмын тодорхойлолт нь үнэндээ ламбда тооцооллын гол цөм бөгөөд түүний үндсэн дээр хандлагыг бий болгодог. функциональ програмчлал.

Анхдагч рекурсив функцууд

Анхан шатны рекурсив функцүүдийн ангилалд үндсэн функцуудмөн операторуудын тусламжтайгаар үндсэн функцуудаас гаргаж авсан бүх функцууд орлуулалтба анхдагч рекурсия.

Үндсэн функцууд нь:

• \ (O () = 0 \) null функц нь үргэлж \ (0 \) буцаадаг аргументгүй функц юм.
• Дарааллын функц \ (S (x) = x + 1 \) нь дурын натурал тоонд өгдөг функц юм \ (x \) дараагийн дугаар\ (x + 1 \)
• Чиг үүрэг \ (I_n ^ m (x_1, \ ldots, x_n) = x_m \), хаана \ (0

Үлдсэн ангийн функцийг бүтээхийн тулд операторуудыг ашигладаг.

• Сэлгээ. \ (M \) хувьсагчдаас \ (f \) функц болон \ (n \) хувьсагчдаас \ (m \) функц \ (g_1, \ ldots, g_m \) -ийн хувьд орлуулалтын үр дүн \ (g_k \) in \ (f \) нь функц юм \ (h (x_1, \ ldots, x_n) = f (g_1 (x_1, \ ldots, x_n), \ ldots, g_m (x_1, \ ldots, x_n)) \)\ (n \) хувьсагчаас.
• Анхдагч давталт. \ (F (x_1, \ ldots, x_n) \) -ийг \ (n \) хувьсагчдын функц, \ (g (x_1, \ ldots, x_ (n + 2)) \) функцийг \ (n + 2 \) хувьсагч. Дараа нь \ (f \) ба \ (g \) функцуудад анхдагч рекурсионы операторыг ашигласны үр дүн нь \ (n + 1 \) хэлбэрийн хувьсагчийн \ (h \) функц юм. \ [h (x_1, \ ldots, x_n, 0) = f (x_1, \ ldots, x_n) \] \ [h (x_1, \ ldots, x_n, y + 1) = g (x_1, \ ldots, x_n, y, h (x_1, \ ldots, x_n, y)) \]

Хэсэгчлэн рекурсив функцууд

Хэсэгчилсэн рекурсив функцүүдийн ангилалд анхдагч рекурсив функцүүд, мөн аргументыг багасгах оператор ашиглан анхдагч рекурсив функцээс олж авсан бүх функцууд орно.

Аргументыг багасгах оператор

\ (F \) нь \ (n \) хувьсагчдын \ (x_i \ in \ mathbb (N) \) функц байг. Дараа нь аргументыг багасгах операторыг \ (f \) функцэд ашигласны үр дүн нь \ (n-1 \) аргументын \ (h \) функц бөгөөд дараах байдлаар тодорхойлогдоно.

\ [h (x_1, \ ldots, x_ (n-1)) = \ min y, \]хаана \ Өөрөөр хэлбэл \ (h \) нь сүүлийн аргументын хамгийн бага утгыг \ (f \) функц руу буцаана.

Анхдагч рекурсив функцуудыг үргэлж тооцоолох боломжтой байдаг боловч зарим аргументийн утгын хувьд хэсэгчлэн рекурсив функцүүдийг тодорхойлох боломжгүй байдаг.

Илүү хатуу, хэсэгчилсэн рекурсив функцуудыг "хэсэгчлэн тодорхойлсон рекурсив функц" гэж нэрлэх ёстой, учир нь тэдгээр нь боломжит аргументын утгуудын зөвхөн нэг хэсэг дээр тодорхойлогддог.

Ерөнхий рекурсив функцууд

Ерөнхий рекурсив функцууд нь аливаа аргументын утгын хувьд тодорхойлогдсон бүх хэсэгчилсэн рекурсив функцүүдийн дэд анги юм. Өгөгдсөн хэсэгчилсэн рекурсив функц нь ерөнхий рекурсив эсэхийг тодорхойлох асуудал юм алгоритмын хувьд шийдвэрлэх боломжгүй... Энэ нь биднийг тооцоолох онолын сэдэв болон зогсоох асуудлыг авчирдаг.

Тооцооллын онол ба зогсоох асуудал

Бидний төсөөлөл нь ерөнхийдөө шийдэгдээгүй асуудлууд, өөрөөр хэлбэл алгоритм зохиох боломжгүй асуудлууд байхыг зөвшөөрдөг.

Тооцоолох онол нь ийм асуудлыг шийддэг.

Алгоритмын хувьд шийдэгдээгүй асуудлын жишээг дурдаж болно асуудлыг зогсоохба ангаахай чанарыг таних асуудал... Тэдгээрийг илүү нарийвчлан авч үзье.

Асуудлыг зогсоох А алгоритмын тайлбар ба оролтын өгөгдөл \ (x \) дээр үндэслэн \ (A \) алгоритм оролтын өгөгдөл \ (x \) дээр зогсох эсэхийг олж мэдэх шаардлагатай.

Зогсоох асуудал нь алгоритмын хувьд шийдэгддэггүй. Үүнийг нотолъё.

\ (\ Дельта \)

Зогсоох асуудлыг шийддэг бүх нийтийн алгоритм байг. Алгоритмыг дүрсэлсэн текстийг боловсруулдаг алгоритмын ангиллыг авч үзье.

Зогсоох асуудлыг шийдэх бүх нийтийн алгоритм байдаг тул дурдсан ангиллын алгоритм өөрийн текст дээр зогсох эсэхийг тодорхойлдог алгоритм байдаг. Ийм алгоритмыг \ (B \) гэж тэмдэглэе.

Өөрийн текстийг боловсруулдаг \ (A \) алгоритмын текст болох оролтын өгөгдөл нь \ (C \) алгоритмыг бүтээцгээе.

1. \ (B \) алгоритмыг \ (A \) дээр гүйцэтгэнэ.
2. Хэрэв \ (B \) алгоритм нь \ (A \) текст дээрээ зогсохыг тодорхойлсон бол 1-р алхам руу очно уу. Үгүй бол 3-р алхам руу очно уу.
3. Алгоритмын төгсгөл \ (C \).

\ (C \) алгоритмыг \ (C \) алгоритмд ашиглахыг оролдсоны дараа бид тодорхой зөрчилдөөнтэй тулгарч байна: хэрэв \ (C \) өөрийн текст дээр зогсвол зогсоож чадахгүй, харин эсрэгээр. Тиймээс \ (B \) алгоритм байхгүй байна. \ (\ биш \ Дельта \)

Зогсоох асуудлыг илүү ерөнхий томъёолох нь ангаахай чанарыг тодорхойлох асуудал юм.

Өсөх чадварыг таних асуудал

Тодорхой цагаан толгой, энэ цагаан толгойн үгс (томъёо), энэ цагаан толгойн үгсийг албан ёсны хөрвүүлэх системийг тодорхойлж өгье (өөрөөр хэлбэл логик тооцоолол хийсэн болно)

Энэхүү логик тооцооллын хүрээнд \ (R \) ба \ (S \) гэсэн хоёр үгэнд \ (R \) - аас \ (S \) хүртэлх дедуктив хэлхээ байдаг уу?

1936 онд Алонзо Сүм Сүмийн теоремыг батлав.

Сүмийн теорем Алдагдлыг хүлээн зөвшөөрөх асуудал нь алгоритмын хувьд шийдэгддэггүй.

Сүм үүнийг батлахын тулд ламбда тооцооллын формализмыг ашигласан. 1937 онд Тьюринг түүнээс үл хамааран ижил теоремыг Тьюрингийн машины формализм ашиглан нотолсон.

Алгоритмын бүх тодорхойлолтууд хоорондоо дүйцэхүйц байдаг тул алгоритмын тодорхой тодорхойлолттой холбоогүй ойлголтын систем байдаг. тооцоолох функц.

Тооцоолох функц Алгоритмаар тооцоолох боломжтой функц.

Алгоритм ашиглан оролт, гаралтын өгөгдлийн хоорондын хамаарлыг тайлбарлах боломжгүй асуудлууд байдаг. Ийм функцууд байдаг тооцоолох боломжгүй.

Тооцоолох боломжгүй функцын жишээ

\ Mathbb (N) \) \ (\ forall n \ in \ mathbb (N) \) -д тодорхойлсон \ (h (n) \) функцийг дараах байдлаар авна уу.

\ [h (n) = \ эхлэл (тохиолдол) 1, & \ текст (хэрэв байгаа бол) \ pi \ текст (яг дараалал байна) n \ text (9-k) \\ 0, & \ текст (өөрөөр бол ) \ төгсгөл (тохиолдлууд) \]

Бид энэ функцийн хувьд \ (1 \) утгыг авч болох боловч \ (0 \) утгыг авахын тулд \ (\ pi \) -ийн хязгааргүй аравтын тэлэлтийг шалгах шаардлагатай бөгөөд энэ нь тодорхой хугацаанд боломжгүй юм. . Тиймээс энэ функцийг тооцоолох боломжгүй юм.

1920-иод оны дараах илэрхийлэл Тооцоолох машинажил гүйцэтгэсэн аливаа машиныг хэлнэ хүний ​​компьютерялангуяа Сүм-Тюрингийн диссертацийн үр дүнтэй аргуудын дагуу боловсруулсан хүмүүст. Энэхүү диссертацийг дараахь байдлаар томъёолсон болно. "Аливаа алгоритмыг зохих Тюринг машин эсвэл хэсэгчлэн рекурсив тодорхойлолт хэлбэрээр тодорхойлж болох бөгөөд тооцоолох функцуудын анги нь хэсэгчилсэн рекурсив функцуудын ангилал, Тьюринг машин дээр тооцоолох функцүүдийн ангилалтай давхцаж байна. . " Өөрөөр хэлбэл, Church-Turing-ийн диссертацийг электрон компьютер гэх мэт механик тооцоолох төхөөрөмжүүдийн мөн чанарын талаархи таамаглал гэж тодорхойлдог. Хангалттай цаг хугацаа, хадгалах зай байгаа тохиолдолд боломжтой бүх тооцоог компьютер дээр хийж болно.

Хязгааргүй тоогоор тооцоолох механизмыг аналог төрөл гэж нэрлэдэг болсон. Ийм механизмын утгыг тасралтгүй тоон утгуудаар илэрхийлдэг, жишээлбэл, босоо амны эргэлтийн өнцөг эсвэл цахилгаан потенциалын зөрүү.

Аналог машинаас ялгаатай нь дижитал машин нь тоон утгын төлөвийг илэрхийлэх, орон бүрийг тусад нь хадгалах чадвартай байв. Дижитал машинууд RAM төхөөрөмжийг бүтээхээс өмнө төрөл бүрийн процессор эсвэл реле ашигладаг байсан.

Нэр Тооцоолох машин 1940 -өөд оноос эхлэн энэ ойлголтыг орлож эхлэв компьютер... Тэдгээр компьютерууд бичиг хэргийн ажилтнуудын хийдэг тооцоог хийж чаддаг байсан. Тухайн үеийн утга нь физик шинж чанараас хамааралгүй болсон тул (аналог машинуудын нэгэн адил) дижитал тоног төхөөрөмж дээр суурилсан логик компьютер дүрслэх боломжтой бүх зүйлийг хийх боломжтой байв. цэвэр механик систем .

Тьюринг машинууд нь тооцоолох чадлын хязгаарлалтыг харгалзан юу тооцож болохыг математикаар албан ёсоор тодорхойлоход зориулагдсан болно. Хэрэв Тюринг машин нь даалгаврыг гүйцэтгэж чадвал даалгаврыг Тюринг тооцоолох боломжтой гэж үзнэ. Тьюринг юуг тооцоолж болохыг тодорхойлох машин зохион бүтээхэд гол анхаарлаа хандуулсан. Тооны ойролцоо утгыг тооцоолж чадах Тьюрингийн машин байгаа л бол энэ утгыг тоолж болно гэж Тьюринг дүгнэжээ. Нэмж дурдахад, Тюринг машин нь AND, OR, XOR, NOT, If-Then-Else гэх мэт логик операторуудыг тайлбарлаж, эсэхийг тодорхойлох боломжтой.