Ցույց տալու համար, որ լեզուն որոշելի է, մեզ անհրաժեշտ է ստեղծելու Turing մեքենա, որը կկանգնի լեզվի այբուբենի ցանկացած մուտքագրման տողի վրա: Քանի որ M-ն dfa է, մենք արդեն ունենք Թյուրինգ մեքենա և պարզապես պետք է ցույց տանք, որ dfa-ն կանգ է առնում յուրաքանչյուր մուտքագրման դեպքում:
Ինչպե՞ս եք հաշվարկում որոշելիությունը:
Լեզուն որոշելի է, եթե և միայն այն դեպքում, երբ այն և նրա լրացումը ճանաչելի են: Ապացույց. Եթե լեզուն որոշելի է, ապա դրա լրացումը որոշելի է (լրացման տակ փակելով):
Ինչպե՞ս եք ապացուցում Թյուրինգի վճռականությունը:
Ապացույց, որ լեզուն, որը ճանաչում է, հավասար է տվյալ լեզվին, և որ ալգորիթմը կանգ է առնում բոլոր մուտքերի վրա: Ապացուցելու համար, որ տվյալ լեզուն Թյուրինգի կողմից ճանաչելի է. Կառուցեք ալգորիթմ, որն ընդունում է հենց այն տողերը, որոնք գտնվում են լեզվումԱյն պետք է կամ մերժի կամ պտտվի լեզվով չհամապատասխանող ցանկացած տողի վրա:
Ինչպե՞ս գիտեք, որ լեզուն ճանաչելի է:
Լեզուն L-ն ճանաչելի է, եթե և միայն այն դեպքում, եթե գոյություն ունի L-ի ստուգիչ, որտեղ ստուգիչը Turing մեքենա է, որը կանգ է առնում բոլոր մուտքերի վրա և բոլոր w∈Σ∗, w∈L↔∃c∈Σ∗. V ընդունում է ⟨w, c⟩:
Ինչպե՞ս ցույց տալ, որ խնդիրն անորոշ է:
Ամբողջության խնդիրն անորոշ է
դադարեցնելու խնդիրը կարող է օգտագործվել ցույց տալու համար, որ այլ խնդիրներ անորոշ են: Ամբողջականության խնդիր. F ֆունկցիան (կամ ծրագիրը) համարվում է ընդհանուր, եթե F(x)-ը սահմանված է բոլոր x-ի համար (կամ նմանապես, եթե F(x)-ը կանգ է առնում բոլոր x-ի համար): Որոշել, թե արդյոք F ֆունկցիան ընդհանուր է, թե ոչ, անորոշ է:
