מספר שאלות במודלים חישוביים.
החלטתי לפצל למספר הודעות בשביל שיהיה מסודר. 1. נתונות שתי בעיות L1, L2. הראתי שבהנתן x לL1 אפשר לבנות ממנו (על ידי הפונ' f) קלט f(x) zzz לבעיה L2 כך ש:
החלטתי לפצל למספר הודעות בשביל שיהיה מסודר. 1. נתונות שתי בעיות L1, L2. הראתי שבהנתן x לL1 אפשר לבנות ממנו (על ידי הפונ' f) קלט f(x) zzz לבעיה L2 כך ש:
f(x)∈L2 ⇒ x∈L1
ובהנתן קלט y ל L2 אפשר לבנות ממנו (על ידי הפונ' g) קלט g zzz לבעיה L1 כך ש:g∈L1 ⇒ y∈L2
הבעיה היא ש g שונה מf, ז"א שבהינתן קלט לL1 אני יכול להפוך אותו לקלט לL2 בדרך מסוימת ובהנתן קלט לL2 אני יכול להפוך אותו לקלט לL1 אבל בדרך אחרת . האם ניתן להסיק מכאן שקיימת רדוקצית מיפוי בין L1 ל L2 ? תודה מראש.