Լուծելիության պրոբլեմ
Լուծելիության պրոբլեմ, զանգվածային պրոբլեմների կարևոր տեսակ։ Կոնստրուկտիվ օբյեկտների որևէ A դասի Լուծելիության պրոբլեմը ավելի ընդհանուր է B դասի նկատմամբ այնպիսի ալգորիթմի կառուցման պրոբլեմն է, որը հնարավորություն է տալիս A-ի ցանկացած տարրի համար պարզելու՝ պատկանո՞ւմ է արդյոք այն B-ին, թե՝ ոչ։ Ձևական համակարգերի ապացուցելիության համար Լուծելիության պրոբլեմ կոչվում է համակարգում ապացուցվող բանաձևերի դասի Լուծելիության պրոբլեմ համակարգի բոլոր բանաձեվերի նկատմամբ։ Այստեղ Լուծելիության պրոբլեմը կապվում է այնպիսի մեթոդի գոյության (կամ չգոյության) հետ, որը հնարավորություն կտա վերջավոր թվով քայլերի միջոցով պարզելու՝ քննարկվող համակարգի որևէ բանաձև արդյո՞ք ապացուցելի (ճշմարիտ) է տվյալ համակարգում, թե՝ այդպիսին չէ։ Այս ըմբռնմամբ Լուծելիության պրոբլեմը դրականորեն է լուծվում ասույթների հաշվում և ձևականացված արիստոտելյան սիլլոգիստիկայում։ Այն հայտնի է նաև Չյորչի թեորեմ[1]։
Ծանոթագրություններ խմբագրել
- ↑ Church, A. (1936). «An unsolvable problem of elementary number theory». American Journal of Mathematics. 58 (2): 345–363. doi:10.2307/2371045. JSTOR 2371045.
|
Սա տրամաբանության մասին անավարտ հոդված է։ Դուք կարող եք օգնել Վիքիպեդիային՝ ուղղելով և լրացնելով այն։ |
Այս հոդվածի կամ նրա բաժնի որոշակի հատվածի սկզբնական կամ ներկայիս տարբերակը վերցված է Քրիեյթիվ Քոմմոնս Նշում–Համանման տարածում 3.0 (Creative Commons BY-SA 3.0) ազատ թույլատրագրով թողարկված Հայկական սովետական հանրագիտարանից (հ․ 4, էջ 677)։ 
|