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

Վիքիպեդիայից՝ ազատ հանրագիտարանից

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

Վերացական մեքենաներին առնչվող խնդիրներ[խմբագրել | խմբագրել կոդը]

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

Մատրիցային առնչվող խնդիրներ[խմբագրել | խմբագրել կոդը]

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

Այլ խնդիրներ[խմբագրել | խմբագրել կոդը]

  • Թույլտվության խնդիր (գերմ.՝ Entscheidungsproblem)
  • Բանաձևի ածանցելիությունը Պեանոյի թվաբանության մեջ
  • 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 աստիճանի հավասարումների համար,
  • Հիլբերտի տասներորդ խնդրի անալոգը ռացիոնալ թվերի հավասարումների համար[6],
  • Մահացող մատրիցային խնդիր 2-րդ կարգի մատրիցաների համար։

Ծանոթագրություններ[խմբագրել | խմբագրել կոդը]

  1. «Life Universal Computer». Արխիվացված օրիգինալից 2014 թ․ հոկտեմբերի 31-ին. Վերցված է 2010 թ․ մայիսի 13-ին.
  2. «When is a pair of matrices mortal?» (PDF). Արխիվացված (PDF) օրիգինալից 2015 թ․ դեկտեմբերի 8-ին. Վերցված է 2010 թ․ մայիսի 6-ին.
  3. Cassaigne, Julien; Halava, Vesa; Harju, Tero; Nicolas, Francois (2014). «Tighter Undecidability Bounds for Matrix Mortality, Zero-in-the-Corner Problems, and More». arXiv:1404.0644 [cs.DM].
  4. Paul C. Bell; Igor Potapov On the Undecidability of the Identity Correspondence Problem and its Applications for Word and Matrix Semigroups(անգլ.) // International Journal of Foundations of Computer Science : journal. — World Scientific, 2010. — Т. 21.6. — С. 963—978. — doi:10.1142/S0129054110007660
  5. Christian Choffrut; Juhani Karhumäki Some decision problems on integer matrices. (und) // ITA. — 2005. — Т. 39(1). — С. 125—131. — doi:10.1051/ita:2005007
  6. Успенский В. А., Семёнов А. Л. Решимые и нерешимые алгоритмические проблемы. // Квант, 1985, № 7, с. 9 — 15