Ալգորիթմորեն անլուծելի խնդիր

Հաշվարկելիության տեսության մեջ ալգորիթմորեն անլուծելի խնդիրն այն խնդիրն է, որն ունի այո կամ ոչ պատասխան յուրաքանչյուր օբյեկտի համար որոշակի մուտքային տվյալների հավաքածուից, որի համար (սկզբունքորեն) չկա որևէ ալգորիթմ, որը, որպես մուտքային տվյալ ստանալով հնարավոր օբյեկտ, կարող է ստանալ այո կամ ոչ՝ կանգ կառնի և վերջավոր թվով քայլերից հետո ցույց կտա ճիշտ պատասխանը։

Վերացական մեքենաներին առնչվող խնդիրներ 

 Դադարեցման խնդիր
 Ինքնակիրառելիության խնդիր
 Busy beaver
 Ռայսի թեորեմում ձևակերպված ցանկացած խնդիր
 Որոշել, թե արդյոք «Կյանք» խաղում տրված նախնական կոնֆիգուրացիան երբևէ կհասնի տվյալ վերջնական կազմաձևին։

Մատրիցային առնչվող խնդիրներ 

 Մահացող մատրիցայի խնդիր. հաշվի առնելով n × n քառակուսի մատրիցների վերջավոր բազմությունը՝ որոշել, թե արդյոք կա այս մատրիցաներից բոլորի կամ որոշների արտադրյալը (հնարավոր է կրկնություններով) ինչ-որ հերթականությամբ, որը տալիս է զրոյական մատրիցա։ Խնդիրն անորոշ է նույնիսկ n=3-ի դեպքում (n=2-ի որոշելիությունը բաց հարց է):
 Նույնականության մատրիցայի խնդիր. հաշվի առնելով n × n քառակուսի մատրիցների վերջավոր բազմությունը՝ որոշել, թե արդյոք կա այս մատրիցներից բոլորի կամ որոշների արտադրյալը (հնարավոր է կրկնություններով) ինչ-որ հերթականությամբ, որը տալիս է նույնականության մատրիցը։ Խնդիրն անորոշ է n=4-ից սկսվող ամբողջ թվային մատրիցների համար և որոշելի n=2-ի համար (n=3-ի որոշելիությունը բաց հարց է)։ Խնդիրը համարժեք է այն հարցին, թե արդյոք մատրիցային կիսախումբը խումբ է։
 Մատրիցային կիսախմբի ազատության խնդիրը ալգորիթմորեն անլուծելի է n=3-ից սկսած ամբողջ թվային մատրիցների համար և բաց է n=2-ի համար։

Այլ խնդիրներ 

 Թույլտվության խնդիր ()
 Բանաձևի ածանցելիությունը Պեանոյի թվաբանության մեջ
 Post correspondence problem
 Կոլմոգորովյան կամայական տողի բարդության հաշվարկ։ Այս հայտարարության կարևոր գործնական հետևանքները ծրագրավորման ոլորտի համար.
 Իդեալական արխիվատոր ստեղծելու անհնարինությունը, որը ցանկացած մուտքային ֆայլի համար ստեղծում է հնարավորինս փոքր չափի ծրագիր, որը տպում է այս ֆայլը,
 իդեալական չափի օպտիմալացնող կոմպիլյատոր ստեղծելու անհնարինությունը,
 Հիլբերտի տասներորդ խնդիրը
 Մասնավորապես, անհնար է հաշվարկել նման ֆունկցիա՝ f(n) = max{min{max{|x_1|, |x_2|, ..., |x_k|: P(x_1, x_2, ..., x_k) = 0}}}, որտեղ k-ը տատանվում է 1-ից մինչև n, P-ն բոլոր բազմանդամների վրա տատանվում է առավելագույնը n աստիճանի k փոփոխականներում, և յուրաքանչյուր անդամի գործակցի մոդուլը չի ​​գերազանցում n-ը։ Այս ֆունկցիայի արժեքը մեզ թույլ է տալիս լուծումների թվարկումը սահմանափակել առավելագույնը n աստիճանի դիոֆանտին հավասարմամբ, առավելագույնը n փոփոխականներով, որոնց գործակիցների մոդուլը չի ​​գերազանցում n-ը։ Օրինակ՝ f(1)=1, f(2)=5 Եթե լիներ f(n-ին համապատասխանող հաշվելի ֆունկցիա), ապա Հիլբերտի տասներորդ խնդիրը կունենար հակառակ լուծումը։
 Որոշել, թե արդյոք տվյալ հարթությունը կարող է ծածկել Վանի սալիկների տրված հավաքածուով։
 Որոշել, թե արդյոք տվյալ հարթությունը կարելի է ծածկել պոլիմինոների տրված հավաքածուով։
 Երկրորդ և ավելի բարձր կարգերի միավորման խնդիրը։
 Տիպի եզրակացության խնդիր Հինդլի-Միլներ տիպի համակարգում՝ N-աստիճանի պոլիմորֆիզմով։

Խնդիրներ, որոնց ալգորիթմական անլուծելիությունն ապացուցված չէ 
Որոշ խնդիրների համար դրանք լուծող ալգորիթմն անհայտ է, և իրենց բնույթով դրանք նման են հայտնի ալգորիթմորեն անլուծելի խնդիրներին։ Նման խնդիրների ալգորիթմական լուծելիության վերաբերյալ հարցերը բաց խնդիրներ են։ Ահա այս առաջադրանքներից մի քանիսը.

 Հիլբերտի տասներորդ խնդրի անալոգը 3 աստիճանի հավասարումների համար,
 Հիլբերտի տասներորդ խնդրի անալոգը ռացիոնալ թվերի հավասարումների համար,
 Մահացող մատրիցային խնդիր 2-րդ կարգի մատրիցաների համար։

Ծանոթագրություններ