Супер Марио Брос. То је немогуће математички решити

Ево две чињенице о математици које се често не рекламирају: Прво, постоје проблеми који се једноставно не могу решити. То не значи да ви лично нисте довољно паметни, или да користите погрешан метод да сазнате; Питање, претпоставку или концепт једноставно нико неће решити. Друго, инспирација за математичке идеје високог нивоа понекад може доћи са неочекиваних места.

Пример: Недавни рад, који се тренутно налази на арКсив серверу за штампање (тј. још увек није рецензиран), и није везан ни за шта осим… Супер Марио Брос.

Једна од 2Д Марио игара објављених од тада Нови Супер Марио Брос.Показали смо да сви осим… Супер Марио Вондер „То се не може утврдити“, каже се у раду, који је написао истраживачки тим из групе Хардинесс из Лабораторије за рачунарске науке и вештачку интелигенцију на МИТ-у.

Чак и за Супер Марио Вондер„Постоје докази који сугеришу да би то могло бити тако[,] Они додају: „На основу тога што догађаји постоје и производе бесконачне Гоомбасе, али је игра још увек веома нова, потребно је више истраживања да би се разумела механика игре довољно добро да би се могло више тврдити о немогућности доношења одлука.

Шта то значи у пракси? Нерешив проблем је, у суштини, оно што звучи: питање на које је немогуће наћи тачан одговор са да или не. У овом случају, проблем је у томе што ви, као играч, заиста желите да будете јаснији – то је једноставно „Може ли се игра победити?“

„Не можете бити теже од овога“, рекао је Ерик Демин, професор рачунарства на МИТ-у и један од аутора рада. Нови свет. „Можете ли доћи до краја, не постоји алгоритам који може одговорити на ово питање у ограниченом временском периоду?

Доказивање нечега оваквог није лак задатак, јер бесконачно играње игре, уз уживање у коришћењу гранта за истраживање, очигледно не долази у обзир. Дакле, уместо тога, тим је користио технологију која је већ била у употреби Пре десет година Дипломирани студент МИТ-а Линус Хамилтон за игру цуе.

„Централна идеја је била да се представи вредност сваког бројача у… цуе У раду се „ниво објашњава бројем непријатеља који заузимају дату локацију на нивоу, искоришћавајући да овај број може бити произвољно велики чак и на нивоу фиксне величине“.

Формалним језиком, тим је постављао машину за бројање: теоријску машину која моделира како рачунар функционише тако што манипулише скупом „бројала“. Врло је једноставно – један бројач унутра Супер Марио Брос. Опремљен је само инструкцијама за „горе“, „доле“ и „скок“, ништа више – али је невероватно користан, јер је у стању да смањи проблем бесконачног броја Гоомба на нешто много лакше: проблем заустављања.

Шта то значи? Па, покрените рачунарски програм и притисните Го – да ли ће програм икада истећи? Или само настави да трчиш заувек? Ово може изгледати као глупо питање, али ово је заглављени проблем – класичан пример нерешивог проблема. Ако би се игра могла свести на проблем заустављања – нпр цуе Могао, и то много Супер Марио Брос. Игре – онда је и то неодлучно.

„Идеја је да нећете моћи да решите овај ниво Марио ако се ови специфични прорачуни не заврше, а знамо да не постоји начин да се то утврди, а самим тим ни начин да се утврди да ли хоћете или не“, рекао је ДеМејн за Нев Сциентист. То може да реши ниво.“

Другим речима: следећи пут када неко каже да губите време играјући глупе видео игрице, не брините – уместо тога можете им рећи да сте… У стварности Решавање нерешивог проблема из области теорије сложености. Гоомбас и разумни диносауруси су само излог.

Студија је објављена на арКсив.