התגובות שלי בפורום
-
תגובות
-
כותרת: אל תשתמשו בקישור, תפתחו חלון חדש ובו את הכתובת
אני מתנצל שוב, הג´יאוסיטיז לא מאפשרים הגעה לתמונות מבחוץ (חידה לא מאוד
מתקדמת: איך הם עושים את זה?). לחילופין, תפתחו חלון חדש ובו תדביקו את
הכתובת ששמתי כבר, או תשתמשו בקישור המצורף לעמוד HTML שאינו יוצר את
הבעיה.כותרת: פתרון
שלום רב,
בקישור המצורף יש את תרשים הפתרון הגיאומטרי ה"טהור". שימו לב לכך שהזוית
שנוצרת על-ידי האלכסון בריבוע השמאלי היא 45 מעלות, והחלק המסובך יותר הוא
להראות שזהו סכום שתי הזויות הנוספות.שימו לב גם לכך שפתרון נומרי אינו מבטיח שזוהי התשובה המדוייקת בכלל (שכן,
הסינוסים של הזוויות הם מספרים אי-רציונליים ואילו המחשבון מייצג אותם בתור
רציונליים בלבד). אני משאיר בתור תרגיל לקוראים לבצע את אותה ההוכחה מבלי
לחשב את ערכם המספרי של הזוויות (רמז: סינוסים ושטח משולש).כותרת: הוכחת המינימליות
ניתן להראות את המינימליות של חיפוש הקלף (כלומר שמספר הפעולות הוא לוגריתמי) על-ידי התבוננות בעץ ההחלטה:
ברור כי ישנם 8 מצבים סופיים (כלפים שאנחנו יכולים להגיע אליהם כפתרון לבעיה). מן הסתם, כל שאלה שנשאל מקטינה את גודל הקבוצה, ולכן למעשה ההכרעה שלנו ביחס לקלף היא תהליך של הליכה על עץ בינארי כאשר כל צומת (עלה או לא-עלה) מציין קבוצת קלפים, בעלים יש קלף יחיד, ובכל צומת-אב יש את איחוד שני הבנים. תהליך ההכרעה הוא בהגעה מהשורש (כל קלף יכול להיות היעד) לעלה מסויים. בעץ בעל n עלים יש לא פחות מ-n צמתים נוספים, ולכן יש בעץ לא פחות מ-2n עלים. העץ המינימלי הוא עץ שלם, וגובהו פרופורציונלי ללוגירתמים מספר הצמתים, ולכן גם ההחלטה אינה יכולה לקחת פחות מסדר גודל לוגריתם של מספר העלים.עתה לגבי הסעיף השני: ניתן בכל שלב של ה"חיפוש" לבדוק את התקיימות התנאי על _שתי_ תתי-הקבוצות, ואם התנאי מתקיים על שתיהן, או לא מתקיים על שתיהן, לחזור לרמה הקודמת (למעלה). בכל מקרה, לא ידרשו יותר משתי "חזרות" כאלה. יחד עם זאת, הכפלנו את מספר השאלות, והוספנו עוד 4 שאלות (לכל היותר), ולכן לפי האלגוריתם ניתן להבטיח את ההגעה לקלף המתאים בעזרת 10 שאלות . מבחינת הסיבוכיות האסימפטוטית, נשארנו בסיבוכיות לוגריתמית, אך אינני בטוח כי זהו הפתרון המינימלי מבחינת הקבועים.
כותרת: תיקון לתיקון של עצמי
What I meant to say is that the fundamental theorem of algebra is formulated for <i>polynomials</i> whose coefficients are complex (belong to C). Moreover, I forgot to mention that n is natural and p is prime.This is what happens when one tries to be excessively fundamentalist in proofs written around 10 P.M. Hopefully this 11 P.M. fix will do.
כותרת: תיקון לתיקון
I have a minor correction to Oren´s proof (which I find very elegant). The fundamental theorem of algebra is formulated for C × C, and while I believe it can be somehow adjusted to field algebra, there´s a simpler way.Lemma: For every natural n, (x ^ 2) mod (p – 1) = 1 only if x mod p = 1 or x mod p = p – 1.
Proof: Let´s persume x is not equal to either 1 or p – 1. Let´s make an equation:
x ^ 2 = np + 1
x ^ 2 – 1 = np
(x + 1)(x – 1) = npOne of the two numbers, x + 1 or x – 1 has to be devidable by p. Because of that, either x mod p = 1 or x mod p = p – 1. We´ve reached a contradiction, and that´s why x has to be either 1 or p – 1.
Application of the lemma to multiplicative field over Zp: for every x´ belonging to the field, x´ * x´ = 1 only if x´ = 1 or x´ = p – 1.
כותרת: As to the energy…
You are right that the energy in the universe is finite. However, the energy is preserved, so that even if your computer "uses" energy, it also "gives" it, in the form of heat, light, radiation etc. It can be proved, though, that the entropy always increases, so that for every amount of energy required, there´s going to be a moment when it will be too dispersed to be useful.כותרת: Java IS infinite
First of all, I´d like to say that both of you (Venndigram and Michael) have raised interesting points throughout our discussion. If the question´s wording had been different, your argument would have solved it. However, since the question is as it is, I still disagree with you.When we talk about Java programs, we sometimes talk about the binaries that are compiled with javac and run with a JRE. That Java, of course, may not run endlessly. But that Java might also have a bug in the compiler, a stack overflow or a spontaneous change of a bit because of a passing gamma-particle from the Sun.
In order to avoid such unpredictable behaviors, we should always talk with a certain degree of abstraction. This Java does not run in our universe; it is abstract. We could, of course, argue whether the abstraction should be infinite in the dimension of time. I think that yes, since otherwise we will have difficulty declaring what is a halt, thus making the whole question senseless.
This abstract Java is in some aspects more powerful than the "real" Java. It is not constrained with things like time or (memory) space. It is fully equivalent to a Turing machine (which has an endless tape). But it still cannot be the means to write an algorithm that checks whether another algorithm halts or not, exactly because of this equivalence.
If you want to put Java in our universe – fine, so be it. But there´s no way it will be capable of answering a question about unlimited time, because any time is limited. And if make it abstract, you still won´t be able to write such an algorithm because Turing proved it impossible.
כותרת: I´ve already made an AI argument
I´ve already written an (counter-)AI argument, under the title "I don´t think it to be another input". It is basically because every AI implementation comes down to the machine code of a CPU, and the machine code is equivalent to an algorithm in Turing´s understanding (a program for a Turing´s machine). So an AI is still algorithmic, and its ability or inability to determine a halt comes down to the previous part of our discussion.Also, please note that concerns about power, disk space or CPU power are not so relevant, the question is abstract. Everything in this universe is finite, however logic is not.
כותרת: I don´t think it to be another input
First of all, if such an algorithm exists, then it must surely have _some_ code. Now for Java you can invoke it with the said-above methods; or you can write a JVM-on-JVM which will do that for you; or you can write an x86 CPU emulator with Java, and use it to run another JVM to run your code, but there must be some way to run it anyway, or how else would you execute it in the first place?Also, note that a software being closed-source does not mean that it is not algorithmic: it always comes down to machine code, which can be disassembled an reused, if such a desire exists.
As to the AI argument, any AI system that one builds with a computer also comes down to the machine code. Now, it is equivalent to an algorithm (a program for a Turing machine), and we´ve already proved that it is impossible to construct a halting algorithm.
One should also note that it is possible to construct a heuristic algorithm which detects some of the halt conditions. (i.e. things like int i = 1; while(i){}). It seems that humans also use some sort of a heuristic to do this. However it is impossible to construct an algorithm that does so for all problems (as we´ve been discussing for a while now).
כותרת: re: Halting Problem
Although it isn´t necessary (as I´ve already said, Turing´s proof is abstract), I´ll try to point out how the proof will work in our case.
You´ll write a function Halt that will decide whether an algorithm expressed by a filename string will halt at a given input or not.
Then I could write an algorithm Trouble, as in the article (with the source called trouble.java). Naturally, if function Halt exists, then I could use it in Trouble (either through Class.byName or simply by copy-and-pasting its source) Then I´ll summon
b = Halt("trouble.java", "trouble.java").
Now you´ll have to answer: is b true or false? If it is either of them, then it is wrong (for the proof, look at the article).כותרת: Re: Halting problem
First of all, the question, "a program Y in Java and input X for it", is equivalent to the phrasing of the halting problem: "Given a description of an algorithm and a description of its initial arguments, determine whether the algorithm, when executed with these arguments, ever halts". So both you and Turing talk about the same thing; I do not see space for discrepancy between you two.Secondly, Turing´s proof is abstract; it needs not be extended into a Java implementation in order to be proved wrong there.
Thirdly, the whole Java thing is deliberately misleading. It is supposed to obscure from you the fact that Java is just another algorithmic language perfectly equivalent to C or Pascal. One should also note that in questions of this nature, space considerations do not count.
And by the way, a Java program (class) can run other Java classes e.g. using Class.ByName() and execute shell commands by Runtime.exec().
Uri
