Nem az a baj, hogy nincs igazad [nem tudom, lehet, igen, lehet, hogy nem], hanem az, hogy a téma szempontjából nem érdekes, amit mondasz.
Nem hiszem, hogy matematikai szempontból éredekes lenne egy olyan program, ami nagyon sok tétel bizonyítását rövid idő alatt megtalálja.
Az első mondatot értem, a másodikat nem értem, hogyan kapcsolódik ide.
Amúgy abban sincs igazad: fontos egy program, amely rövid idő alatt sok tétel bizonyítását megtalálja (gyorsabban, mint más programok).
Ami az első mondatodat illeti.
- Még egyszer: legyen L 0-adrendű nyelv, sok ilyen van, programnyelvek is lehetnek akár. Legyen L nem-rekurzív.
Legyen most "xywwwxywx" egy szó, amelyről nem tudjuk, hogy benne van-e L-ben?
Ha nem, akkor ezt nem is lehet általánosan, algoritmusasal megoldani, HISZEN L komplementere nem generálható grammatikával.
Ezt a tételt nyilván Te is ismered: vannak nem-felsorolható, grammatikával generálhatatlan nyelvek (amelyek komplementere grammatikával generálható).
((Mondok egy ilyen nyelvet, jó? Vegyük azon CF grammatika-párokat, mint szavakat, amelyek ugyanazt a nyelvet generálják. Ez a nyelv sem generálható generatív grammatikával.
Vagy: azokat a CS grammatikákat, mint szavakat, amelyek CF nyelvet generálnak. Ez a nyelv sem 0-adrendű.))
Folytatva:
úgy szeretnénk valami választ kapni, xywwwxywx L-beliségére! Ha benne van, elég L-et generálni, de aha nincs benne:
van bizonyos lehetőség, bár nem egyszerű (ezért lázadozol az igazolásom bonyolultsága miatt).
Ez az állításom. A tétel különben még nem teljes, de mint mondtam, a Metamatematika topkba írom a végét.
Ez nem fontos nyelvelméletileg??
Persze a linked is fontos problémákat említ, azokat is tisztelem. Csakhogy én most nem azokkal foglalkoztam.
Van ez így:)
|