ТЬЮ́РИНГА МАШИ́НА

ТЬЮ́РИНГА МАШИ́НА, на­зва­ние, за­кре­пив­шее­ся за аб­ст­ракт­ны­ми (во­об­ра­жае­мы­ми) вы­чис­ли­тель­ны­ми ма­ши­на­ми не­ко­то­ро­го точ­но оха­рак­те­ри­зо­ван­но­го типа, даю­щи­ми уточ­не­ние об­ще­го ин­туи­тив­но­го пред­став­ле­ния об ал­го­рит­ме. Кон­цеп­ция та­ко­го ро­да ма­ши­ны сло­жи­лась в сер. 1930-х гг. у А. Тью­рин­га в ре­зуль­та­те про­ве­дён­но­го им ана­ли­за дей­ст­вий че­ло­ве­ка, вы­пол­няю­ще­го в со­от­вет­ст­вии с за­ра­нее раз­ра­бо­тан­ным пла­ном те или иные вы­чис­ле­ния, т. е. по­сле­дова­тель­ные пре­об­ра­зо­ва­ния зна­ко­вых ком­плек­сов.

Т. м. мож­но пред­став­лять в ви­де не­ко­то­ро­го ав­то­ма­ти­че­ски дей­ст­вую­ще­го уст­рой­ст­ва, ко­то­рое мо­жет на­хо­дить­ся в ко­неч­ном чис­ле внутр. со­стоя­ний и ко­то­рое снаб­же­но бес­ко­неч­ной внеш­ней па­мя­тью – лен­той. Сре­ди со­стоя­ний име­ют­ся два вы­де­лен­ных – на­чаль­ное и за­клю­чи­тель­ное. Лен­та раз­де­ле­на на клет­ки (ячей­ки) и не ог­ра­ни­че­на вле­во и впра­во. В ка­ж­дой клет­ке лен­ты мо­жет быть за­пи­сан лю­бой из сим­во­лов, вхо­дя­щих в не­ко­то­рый за­ра­нее за­дан­ный пе­ре­чень (ра­ди еди­но­об­ра­зия счи­та­ют, что в пус­той клет­ке за­пи­са­на «пус­тая бу­к­ва»). В ка­ж­дый (дис­крет­ный) мо­мент вре­ме­ни Т. м. на­хо­дит­ся в од­ном из сво­их со­стоя­ний и, рас­смат­ри­вая (по­сред­ст­вом спец. уст­рой­ст­ва) од­ну из кле­ток лен­ты, вос­при­ни­ма­ет за­пи­сан­ный в ней сим­вол. Ес­ли в те­ку­щий мо­мент вре­ме­ни Т. м. на­хо­дит­ся в не­за­клю­чи­тель­ном со­стоя­нии, то в сле­дую­щий за ним мо­мент: она пе­ре­хо­дит в но­вое со­стоя­ние, быть мо­жет сов­па­даю­щее со ста­рым или за­клю­чи­тель­ное; в рас­смат­ри­вае­мой клет­ке ста­рый сим­вол за­ме­ня­ет­ся но­вым, мо­жет быть пус­тым или сов­па­даю­щим со ста­рым; лен­та Т. м. сдви­га­ет­ся на од­ну клет­ку вле­во или впра­во ли­бо ос­та­ёт­ся на мес­те. Этот шаг Т. м. впол­не оп­ре­де­ля­ет­ся её те­ку­щим со­стоя­ни­ем и те­ку­щим вос­при­ни­мае­мым сим­во­лом. Таб­ли­ца, со­дер­жа­щая пол­ное пе­ре­чис­ле­ние воз­мож­ных ша­гов дан­ной Т. м., на­зы­ва­ет­ся про­грам­мой этой ма­ши­ны.

Те­ку­щее пол­ное опи­са­ние Т. м. да­ёт­ся её кон­фи­гу­ра­ци­ей, ко­то­рая со­сто­ит из ука­за­ния для дан­но­го мо­мен­та сле­дую­щей ин­фор­ма­ции: кон­крет­но­го за­пол­не­ния кле­ток лен­ты сим­во­ла­ми; клет­ки, на­хо­дя­щей­ся в по­ле зре­ния ма­ши­ны; со­стоя­ния, в ко­то­ром ма­ши­на на­хо­дит­ся.

Ес­ли для дан­ной Т. м. взять в ка­че­ст­ве ис­ход­ной к.-л. кон­фи­гу­ра­цию с не­за­клю­чи­тель­ным со­стоя­ни­ем, то ра­бо­та этой ма­ши­ны бу­дет за­клю­чать­ся в по­сле­до­ва­тель­ном, шаг за ша­гом, пре­об­ра­зо­ва­нии ис­ход­ной кон­фи­гу­ра­ции в со­от­вет­ст­вии с про­грам­мой ма­ши­ны до тех пор, по­ка не бу­дет дос­тиг­ну­та кон­фи­гу­ра­ция с за­клю­чи­тель­ным со­стоя­ни­ем. Эта по­след­няя, ес­ли она су­ще­ст­ву­ет, счи­та­ет­ся ре­зуль­та­том ра­бо­ты дан­ной Т. м. над ис­ход­ной кон­фи­гу­ра­ци­ей.

Име­ют­ся серь­ёз­ные ос­но­ва­ния счи­тать, что по­ня­тие Т. м. дос­тав­ля­ет аде­к­ват­ное пред­став­ле­ние об ал­го­рит­ме, т. е. вся­кий ал­го­ритм мо­жет быть про­мо­де­ли­ро­ван под­хо­дя­щей Т. м. Со­от­вет­ст­вую­щее со­гла­ше­ние из­вест­но в ал­го­рит­мов тео­рии под на­зва­ни­ем те­зи­са Тью­рин­га. Тео­рия Т. м. да­ёт удоб­ный ра­бо­чий ап­па­рат для мн. ис­сле­до­ва­ний, тре­бую­щих точ­но­го по­ня­тия ал­го­рит­ма. В хо­де раз­ви­тия тео­рии Т. м. рас­смат­ри­ва­лись их раз­лич­ные обоб­ще­ния (напр., Т. м. с не­сколь­ки­ми лен­та­ми, а так­же не­де­тер­ми­ни­ро­ван­ные Т. м.).