Диофантови предикати

Предполагем, че ако някой обясни на всички нас как можем да решим долната задача, всички ще останем доволни. Надявам се, че въпреки сложно, проблемът не е нерешим, и може да носи изгода (за програмистите най-вече). ЗАДАЧА: В теория на рекурсията се твърди, че всеки полу-рекурсивен предикат е диофантов (виж теоремата на Матиасевич). С други думи, всяко р.п. множеството от цели числа (или n-ки от цели числа), което се определя от даден полу-рекуесивен предикат се състои от всевъзможните целочислени решения на някой полином от една или повече променливи с целочислени коефициенти и степени. В областта Image Processing или криптографията, например, има много трудоемки алгоритми. Понеже повечето задачи (алгоритми) в програмирането биха могли да се сведат до полу-рекурсивен предикат, имам (поне) два въпроса: 1. Как един алгоритъм да <дефинираме> като полу-рекурсивен предикат и след това да го <преобразуваме> в диофантово уравнение? 2. Как след това лесно да решим това уравнение? (например бихме ли могли да използваме първо някой метод за приблизително решение, дори в комплексна област, а после да <изтестваме> дали тези решения са целочислени) Например, може ли някой да демонстрира тази техника, да речем с някой елементарен алгоритъм за сортировка? (в този случай решенията на съответния диофантов предикат биха могли да бъдат множество двойки (i, j), което ще ни показва, че i-тия елемент след сортирането ще стане j-ти елемент) Ако това не може да стане(не е известен общ метод), имаме ли тук нещо общо с голямата теорема на Ферма?

Логиката не ми беше любима дисциплина ( най - вече заради проф. Скордев ), та съм позабравил доста понятия, а някои със сигурност и никога не съм знаел. Тъй като съм математик по образование ( почти завършено ) и работя програмист ми е много интересно това , за което става въпрос тук. Какво са : 1. предикат 2. полу-рекурсивен предикат 3. диофантов предикат и всички други понятия , явяващи се само в речника на логиката. Благодаря предварително

:) Здрасити! На мен също не ми е много ясно, и за това питам. Аз също съм програмист, но изобщо не съм математик. Длъжен съм да се ДОИЗЯСНЯ. В смисъла на тази тема, която започах тук, имам в предвид следното(само идеята): В теория на рекурсията работим само с натуралните числа, така че променливите приемат само натурални числа, функциите връщат(ако изобщо могат:) натурални числа и въпросните функции са "частично рекурсивни"-те, както се определят. Може да вземем числото 0 да означава "лъжа", а числото 1 - "истина". Сега, N-арен "рекурсивен предикат" ще е чстично рекурсивна функция ф(x1, ..., xN), която __винаги__ ни връща 0 или 1 за всички натурални числа, никога не <зацикля>(тотална е), а множеството което определя тази функция(гледана като характеристическа) се нарича "рекурсивно". За разлика от това, "полу-рекурсивен предикат" връща 1=истина в дефиниционната си област, а извън нея може да върне 0=лъжа, но също се допуска и да <зацикли> (т.е нищо да не ни върне, да не е определена там, да не е тотална). Съответното множество което се определя(т.е. деф.облст на предиката) наричаме "рекурсивно преброимо" или съкратено "р.п.". Относно думата "диофантов" предикат, може и да съм сгрешил, но така си спомням(горе-долу), че се използваше в една книга. Там беше писано много малко, и доказателството на теоремата на Матиасевич я нямаше(а само формулировката). Може би ако видя(и разбера:) едно <конструктивно> доказателство на тази теорема, изобщо няма да питам повече по този въпрос? ОБЕЩАВАМ, че довечера ще направя справка в книгата за която говоря, ще кажа коя е книгата(в момента не си спомням подробноисти) и ще цитирам точно, ако трябва! ГРЕШКА! Аз съм писал по-горе в тази тема "решения на някой полином", което не означава нищо, и някой истински математик с основание трябва да ми счупи главата. Да се разбира "НУЛИ НА НЯКОЙ ПОЛИНОМ", т.е. ако приравним на нула този израз (съответен на полинома) и тогава потърсим онези цели стойности, за които въпросното равенство се удоволетворява.