Ապացույց, որ գոյություն ունի առնվազն մեկ չնչին համակարգչային ծրագիր, որը գոյություն չունի

Ամենագեղեցիկ մաթեմատիկական ապացույցները, հատոր: 2, Maxime Coutte.

Անցյալ շաբաթվա հոդվածը վերաբերում էր. «Որոշ անսահմանություններ ավելի մեծ են, քան մյուսները»: և Կանտորի դիագոնալ փաստարկը: Այս շաբաթ ես ուզում եմ կիսվել իմ սիրած տեսական համակարգչային գիտության խնդիրներից մեկը:

«Մասեր չորս վաղ համակարգիչներից, 1962 թվականից.

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

Սահմանելով H, անհնար համակարգչային ծրագիրը

Մենք սահմանում ենք համակարգչային ծրագիր P (i) որպես ցուցում P ցուցումների ցանկ, որոնք, երբ իրականացվում են i- ով մուտքագրմամբ, տալիս է ելքային o:

Օրինակ,

ծրագիր է, որն ամփոփում է այն երկու համարները, որոնք դուք տալիս եք որպես մուտք, և

ծրագիր է, որն օգտագործում է մեկ այլ ծրագիր `P_add - որպես մուտք, և անցնում է այս ծրագրին մնացած երկու մուտքերը: Դա անում է այն, ինչ անում է P_add- ը (a, b) և կրկնապատկում է այն:

Երբ ծրագիրն իրականացվում է, այն կարող է խրվել, վազել ընդմիշտ և երբեք ոչինչ չարտադրել, օրինակ ՝ P_sum ծրագիրը, որն անցնում է բոլոր բնական թվերի գումարին, կշարունակի ավելացնել բնական թվեր ընդմիշտ ՝ առանց վազքի ավարտման (այսինքն ՝ դադարեցնելու) և արդյունքը բերելով:

Հիմա եկեք ենթադրենք, որ այն գոյություն ունի ծրագիր H (P, i), որը որպես մուտքագրում է P (i) ծրագրի P (i) ծրագրի P հրահանգների ցուցակը, և ես մուտքագրում P (i), և ելք a 1-ից, եթե P (i) դադարեցրեք ինչ-որ պահի և 0-ը, եթե P (i )- ը խրված է և վազում է ընդմիշտ: Պարզ ասած,

Ինչու տրամաբանական ցուցումների ցանկը հնարավոր չէ գոյություն ունենալ

Հիմնվելով Ալան Տուրինգի ապացույցի վրա «Հաշվողական համարների համար ՝ Entscheidungsproblem- ով դիմում» -1937-ում, մենք կապացուցենք, որ Հ-ն գոյություն չունի:

Ելնելով ենթադրությունից, որ H գոյությունը մենք կառուցում ենք ծրագիր X (P), որը հավերժ կաշխատի, եթե և միայն եթե H (P, P) = 1 և դադարեցվի, եթե և միայն եթե H (P, P) = 0. Այլ կերպ ասած,

Մենք այժմ կարող ենք համարել X (i) հրահանգների սեփական ցանկը ՝ որպես մուտքագրում. X (X):

Հետևաբար X (X) վազում է ընդմիշտ, եթե և միայն այն դեպքում, եթե H (X, X) = 1 և X (X) դադարեցվի, եթե և միայն եթե H (X, X) = 0. այլ կերպ ասած,

Մենք հակասություն ունենք: Մենք Reductio ad absurdum- ի կողմից ցույց տվեցինք, որ Հ-ն չի կարող գոյություն ունենալ, քանի որ դրա գոյությունը անհեթեթ եզրահանգումների է հանգեցնում:

Հետևաբար, համակարգչային ծրագիր, որը կարող է որոշել, թե որևէ համակարգչային ծրագիր, որին տրված է որևէ մուտք, խրված է և գործելու է ընդմիշտ, կամ գործարկելն անհնար է: Գոյություն ունի առնվազն մեկ Համակարգչային ծրագիր, որը լուծում է տրամաբանական խնդիրը, որը, հնարավոր է, գոյություն չունի:

Հղումներ ՝ Ալան Թուրինգ. «Հաշվարկելի համարների վրա ՝ Entscheidungsproblem դիմումով»: 1937 թ.

Ես Max Coutte- ն եմ, Relativty.com- ի համահիմնադիր, VR ականջակալ, որը ես պատրաստել եմ զրոյից, որից ես բացել եմ կոդն ու ապարատը: Հետևեք ինձ Twitter- ում `maxcoutte: