Constructive Models - 9780306110665

Teoria modeli konstruktywnych (rekurencyjnych) wywodzi się z prac Froehlicha, Shepherdsona, Mal'tseva, Kuzniecowa, Rabina i Vaughta z lat 50. XX wieku. W ramach tej teorii bada się właściwości algorytmiczne modeli abstrakcyjnych poprzez konstruowanie reprezentacji na zbiorze liczb naturalnych i badanie zależności pomiędzy właściwościami algorytmicznymi i strukturalnymi tych modeli. Książka ta stanowi bardzo czytelny wykład współczesnej teorii modeli konstrukcyjnych i opisuje metody i podejścia opracowane przez przedstawicieli syberyjskiej szkoły algebry i logiki oraz kilku innych badaczy (w szczególności Nerode'a i jego współpracowników). Głównymi tematami są istnienie modeli rekurencyjnych i zastosowania do pól, algebr i zbiorów uporządkowanych (Ershov), istnienie rozstrzygalnych modeli pierwszych (Goncharov, Harrington), istnienie rozstrzygalnych modeli nasyconych (Morley), istnienie rozstrzygalnych jednorodnych modele (Goncharov i Peretyat'kin), własności teorii Ehrenfeuchta (Millara, Asha i Reeda), teorię wymiaru algorytmicznego i warunków autostabilności (Goncharov, Ash, Shore, Khusainov, Ventsov i inni) oraz teorię klas obliczeniowych modeli o różnych właściwościach. Omówiono także przyszłe perspektywy teorii modeli konstrukcyjnych. Większość wyników zawartych w książce po raz pierwszy została zaprezentowana w formie monografii. Teoria modeli konstrukcyjnych służy jako podstawa matematyki rekurencyjnej. Jest również przydatny w informatyce, w szczególności przy badaniu języków programowania, języków specyfikacji wyższego poziomu, abstrakcyjnych typów danych oraz problemów syntezy i weryfikacji programów. Dlatego też książka będzie przydatna nie tylko specjalistom logiki matematycznej i teorii algorytmów, ale także naukowcom zainteresowanym matematycznymi podstawami informatyki. Autorzy są wybitnymi specjalistami w dziedzinie logiki matematycznej. Ustalili podstawowe wyniki w zakresie teorii elementarnych, teorii modeli, teorii algorytmów, teorii pola, teorii grup, logiki stosowanej, numeracji obliczeniowych, teorii modeli konstrukcyjnych i informatyki teoretycznej.