– Daar word gesê dat 'n besluitprobleem P semi-beslisbaar is (d.w.s. het 'n semi-algoritme) as die taal L van alle ja-gevalle tot P r.e. – (Ekwivalensieprobleem vir DFA) Gegewe twee DFA's, aanvaar hulle dieselfde taal? Bewys: Onthou Cantor se argument van eerste lesing.
Wanneer gesê word dat 'n probleem semi-beslisbaar is?
Semi-beslisbare probleme is dié vir wat 'n Turing-masjien stop op die insette wat daardeur aanvaar word, maar dit kan óf stop óf vir ewig loop op die insette wat deur die Turing-masjien verwerp word. Sulke probleme word as Turing Herkenbare probleme genoem.
Wat is gedeeltelik beslisbare probleem?
Definisie: Een wie se geassosieerde taal 'n rekursief optelbare taal is. Eweneens bestaan daar 'n algoritme wat stop en 1 uitstuur vir elke geval met 'n "ja"-antwoord, maar vir gevalle met 'n "nee"-antwoord word toegelaat om óf nie te stop nie óf om te stop en 0 uit te voer.
Is stopprobleem gedeeltelik besluitbaar?
Alan Turing het in 1936 bewys dat 'n algemene algoritme wat op 'n Turing-masjien loop wat die stopprobleem vir alle moontlike programinvoerpare oplos, noodwendig nie kan bestaan nie. Daarom is die stopprobleem onbeslisbaar vir Turing-masjiene.
Waarom is die stopprobleem semi-beslisbaar?
Daar word gesê dat 'n taal semi-beslisbaar is as daar 'n Turing-masjien bestaan wat stop as 'n woord aan die taal behoort (JA-gevalle) en kan verwerp of oneindig ingaan lus as die woord nie aan die taal behoort nie (GEEN geval).
