Тюринг машинасы танитын тіл, анықтамасы бойынша, ол қабылдайтын жолдар жинағы. Құрылғыға кіріс берілгенде, ол қабылданады немесе қабылданбайды.
Тьюринг машинасы қай тілді қабылдайды?
ТМ тілді кез келген кіріс жолы үшін соңғы күйге кірсе, w қабылдайды. Тіл рекурсивті түрде санауға болады (түрі-0 грамматикасы арқылы жасалған), егер ол келесі арқылы қабылданса Тьюринг машинасы. ТМ оны қабылдаса және тілде емес кез келген енгізу үшін қабылдамаушы күйге енсе, тілді шешеді.
Тюринг арқылы танылатын тіл дегеніміз не?
Тюринг арқылы танылатын тіл егер осы тілдегі жолдарды ғана тоқтатып, қабылдайтын машина болса, сол тілде емес, ол TM не қабылдамайды, не мүлде тоқтамайды.… Кейбір Тьюринг машинасы оны танитын болса, тіл Тьюринг танылатын деп аталады.
Тюринг машинасы тілді қабылдай ма?
туринг машинасырекурсивті түрде санауға болатын болса да, барлық тілді қабылдайды. Рекурсивті - бір ережелер жинағын кез келген рет қайталауды білдіреді және санауға болатын элементтер тізімін білдіреді.
ТМ тілі қандай?
ТМ тілі ол қабылдайтын барлық жолдардың жинағы ретінде анықталады. Әрбір тіл Тьюринг машинасының тілі бола бермейді – бұл теориялық информатиканың маңызды нәтижелерінің бірі.
