Logo hy.boatexistence.com

Ո՞ր լեզուն է ճանաչվում Turing մեքենայի կողմից:

Բովանդակություն:

Ո՞ր լեզուն է ճանաչվում Turing մեքենայի կողմից:
Ո՞ր լեզուն է ճանաչվում Turing մեքենայի կողմից:

Video: Ո՞ր լեզուն է ճանաչվում Turing մեքենայի կողմից:

Video: Ո՞ր լեզուն է ճանաչվում Turing մեքենայի կողմից:
Video: Տղամարդու 4 գաղտնիք, որ յուրաքանչյուր կին պետք է իմանա 2024, Մայիս
Anonim

Թյուրինգի մեքենայի կողմից ճանաչված լեզուն, ըստ սահմանման, տողերի բազմությունն է, որը նա ընդունում է: Երբ մուտք է տրվում մեքենային, այն կա՛մ ընդունվում է, կա՛մ ոչ:

Ո՞ր լեզուն է ընդունում Թյուրինգ մեքենան:

A TM-ն ընդունում է լեզու, եթե այն մտնում է վերջնական վիճակի ցանկացած մուտքային տողի համար w Լեզուն ռեկուրսիվորեն թվարկվում է (ստեղծվում է Type-0 քերականությամբ), եթե այն ընդունվում է Թյուրինգի մեքենա: TM-ն որոշում է լեզուն, եթե այն ընդունում է այն և մտնում է մերժման վիճակի մեջ ցանկացած մուտքագրման համար, որը լեզվում չէ:

Ի՞նչ է Թյուրինգի ճանաչելի լեզուն:

Լեզու, որը ճանաչելի է Թյուրինգի եթե կա մի մեքենա, որը կդադարեցնի և կընդունի միայն այդ լեզվի տողերը և ոչ թեայդ լեզվով, ապա այդ TM-ը կամ մերժում է, կամ ընդհանրապես չի դադարում.… Լեզուն կոչվում է Թյուրինգ ճանաչելի, եթե որոշ Թյուրինգ մեքենա ճանաչում է այն:

Թյուրինգ մեքենան ընդունում է լեզուն:

թուրինգ մեքենան ընդունում է ամբողջ լեզուն, չնայածդրանք ռեկուրսիվորեն թվարկելի են: Ռեկուրսիվ նշանակում է կրկնել կանոնների միևնույն շարքը ցանկացած թվով անգամ, իսկ թվարկելը նշանակում է տարրերի ցանկ:

Ի՞նչ է TM-ի լեզուն:

ՏՄ-ի լեզուն սահմանվում է որպես այն բոլոր տողերի բազմությունը, որը նա ընդունում է: Ոչ բոլոր լեզուներն են Թյուրինգի մեքենայի լեզուն, սա համակարգչային գիտության տեսական արդյունքներից մեկն է:

Խորհուրդ ենք տալիս: