Lösbarhetsproblem

Lösbarhetsproblem ( avgörbarhetsproblem ) är en fråga formulerad inom ramen för något formellt system som kräver ett ja eller nej svar, möjligen beroende på värdena för vissa ingångsparametrar [ 1] .

Till exempel problemet "med två siffror: och ; är delbart med ? är ett lösbarhetsproblem. Svaret kan ges antingen "ja" eller "nej" och beror på värdena för och . En metod för att lösa ett lösbarhetsproblem, presenterad i form av en algoritm, kallas beslutsprocedur för detta problem. Således bör lösningsproceduren för problemet från exemplet ovan bestämma uppsättningen av åtgärder som bör vidtas för att kontrollera heltalsdelbarheten för givna tal . En av dessa algoritmer - division med en kolumn  - studeras i grundskolan. En återstod lika med noll betyder att svaret är "ja", annars - "nej". Ett lösbarhetsproblem för vilket det finns ett lösande förfarande kallas lösbart.

Alla matematiska problem kan inte formuleras som lösbarhetsproblem. Att beräkna produkten av två tal, hitta den snabbaste algoritmen för att multiplicera tal och optimeringsproblem , i synnerhet det klassiska resandeförsäljarproblemet , är inte lösbarhetsproblem, eftersom de inte kan formuleras på ett sådant sätt att svaret på problemet skulle vara " Ja eller nej".

Forskning inom området rekursionsteori fokuserar ofta på avgörbarhetsproblem, eftersom många problem kan reduceras till dem utan förlust av generalitet.

Se även

• Tillståndsproblem
• Algoritmisk avgörbarhet

Anteckningar

1. ↑ Tom Stewart. Datorteori för programmerare . — Liter, 2015-06-24. - S. 329. - 386 sid. — ISBN 9785457831230 .

Litteratur

• Maltsev A. I. , Algoritmer och rekursiva funktioner , Nauka, 1986.
• Daniel Kroening & Ofer Strichman, Decision procedures , Springer, ISBN 978-3-540-74104-6
• Hartley Rogers, Jr., The Theory of Recursive Functions and Effective Computability , MIT Press , ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1