Ինչպե՞ս ապացուցել վճռականությունը:

2024 Հեղինակ: Fiona Howard | [email protected]. Վերջին փոփոխված: 2024-01-10 06:38

Ցույց տալու համար, որ լեզուն որոշելի է, մեզ անհրաժեշտ է ստեղծելու Turing մեքենա, որը կկանգնի լեզվի այբուբենի ցանկացած մուտքագրման տողի վրա: Քանի որ M-ն dfa է, մենք արդեն ունենք Թյուրինգ մեքենա և պարզապես պետք է ցույց տանք, որ dfa-ն կանգ է առնում յուրաքանչյուր մուտքագրման դեպքում:

Ինչպե՞ս եք հաշվարկում որոշելիությունը:

Լեզուն որոշելի է, եթե և միայն այն դեպքում, երբ այն և նրա լրացումը ճանաչելի են: Ապացույց. Եթե լեզուն որոշելի է, ապա դրա լրացումը որոշելի է (լրացման տակ փակելով):

Ինչպե՞ս եք ապացուցում Թյուրինգի վճռականությունը:

Ապացույց, որ լեզուն, որը ճանաչում է, հավասար է տվյալ լեզվին, և որ ալգորիթմը կանգ է առնում բոլոր մուտքերի վրա: Ապացուցելու համար, որ տվյալ լեզուն Թյուրինգի կողմից ճանաչելի է. Կառուցեք ալգորիթմ, որն ընդունում է հենց այն տողերը, որոնք գտնվում են լեզվումԱյն պետք է կամ մերժի կամ պտտվի լեզվով չհամապատասխանող ցանկացած տողի վրա:

Ինչպե՞ս գիտեք, որ լեզուն ճանաչելի է:

Լեզուն L-ն ճանաչելի է, եթե և միայն այն դեպքում, եթե գոյություն ունի L-ի ստուգիչ, որտեղ ստուգիչը Turing մեքենա է, որը կանգ է առնում բոլոր մուտքերի վրա և բոլոր w∈Σ∗, w∈L↔∃c∈Σ∗. V ընդունում է ⟨w, c⟩:

Ինչպե՞ս ցույց տալ, որ խնդիրն անորոշ է:

Ամբողջության խնդիրն անորոշ է

դադարեցնելու խնդիրը կարող է օգտագործվել ցույց տալու համար, որ այլ խնդիրներ անորոշ են: Ամբողջականության խնդիր. F ֆունկցիան (կամ ծրագիրը) համարվում է ընդհանուր, եթե F(x)-ը սահմանված է բոլոր x-ի համար (կամ նմանապես, եթե F(x)-ը կանգ է առնում բոլոր x-ի համար): Որոշել, թե արդյոք F ֆունկցիան ընդհանուր է, թե ոչ, անորոշ է: