Nekonstruktivitātes daudzums induktīvajā izvedumā

2010

Induktīvā izveduma modelis, oriģināli piedāvātais Gold, tiek papildināts ar Freivalda definēto nekonstruktīvās skaitļošanas mehānismu. Abstraktais skaitļošanas modelis ar palīdzību, definētais analizējot nekonstruktīvo modeli salīdzinājumā ar citiem modeļiem ar palīdzību, ir izmantots par pamatu, lai definētu trīs nekonstruktīvas variācijas induktīvā izveduma modelim. Tiek pētītas vairākas šo modeļu īpatnības. Dažiem zināmiem konstruktīvi neatrisināmiem uzdevumiem tiek dots nekonstruktīvais atrisinājums, kā arī tiek uzradīta virkne jaunu nekonstruktīvi atrisināmu uzdevumu. Tiek pētīts gan funkciju, gan valodu izvedums. Dažu uzdevumu risināšanā tiek izmantota Kolmogorova sarežģītība. Tiek pē…