- This topic has 26 תגובות, 7 משתתפים, and was last updated לפני 23 שנים, חודש 1 by
.
-
תגובות
-
Hi!
I´ve just discovered(playing with the "test yourself") that your answer to q.32(about a program in JAVA which will determine whether another program will eventually stop running or not with a given input) is that it is impossible. This answer doesn´t seem right to me:
although nowadays we don´t have computers that can think, nobody proved it´s impossible. Actually, assuming the human brain is just many neurons, we could, theoritically, just put all the system into a program, although it might take some time.
I guess we agree that a human can determine whether a program will end running(by proving the appropriate theorem – it´s complicated, but it can always be done -except for such cases as the continuum hypothesis, when a theorem cannot be proved, but such a problem will never arise – and it´s easily proved – when we are dealing with an algorithm). Hence, a computer that imitates human brain can do it as well.
So, i think the right answer is the second one – yes, it´s possible, but it will take a long time to program such a thing – but defenitely a finite time.
There is the issue of algorithms that involve random numbers, but here we can use proving theorems(even involving limits) and the fact that the numbers aren´t so much random – they´re limited by the computer´s memory(i mean the physical one, not the double, int etc. limitations).
Generally, I really liked some questions (especially, the question about pi in the first stage -it was somehow similar to this one, i think).
Do you have any comments? Can you still change my mark
?(i took, apparently, 11th place, so it would be nice to be in the top 10……).
Thank you for your patience and answer(if it will come…)
Michael Guerzhoyכותרת: אי-אפשר להרכיב אלגוריתם כזה
הוכח על-ידי טיורינג שלא ניתן להרכיב אלגוריתם F שיקבע בשביל כל אלגוריתם X והקלט Y עבורו אם האלגוריתם X יתבצע תוך זמן סופי או לא. ראה את הקישור המצורף בשביל הסבר פשוט ומובן (נדרש גאון בשביל להמציא את ההוכחה המקורית).כותרת: halting problem
Indeed, Turing knew what he was talking about. I didn´t read the original proof, but suppose the proof in the link you´ve sent is similar to it. Sure, in a way, Turing is right. There is one problem with it, as I see it. The function "Trouble" is able to call function
"Halt".
So, as I see it, Turing claims the following: show me your algorithm that determines whether a given algorithm with a given input will evetually halt, and i´ll find such an input that will prove that your algorithm is bad. The thing is that you must have additional input for this. And if your program gets ANY additional input, the problem is not interesting: say, if it connects to your site, which says whether to stop running or not.Morever, show me a JAVA application which activates another application.
One more thing – the proof doesn´t consider the fact that we have limited memory. What if the Halt function is programmed in such a way that it takes more then a half of the memory, or just deosn´t allow to copies to run in the same time?
Consider my analogy to the human brain in the first post. It won´t work witb us humans, would it?
Sure, a paradox can confuse us, but does it mean we are unable to determine whether an algorithm will stop running?
And that´s exactly the case.If someone asks why does a cat have three legs, we´ll just answer – because it doesn´t, that´s why
To be short, Turing is right and I am right. No contradiction. I think
כותרת: 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
כותרת: לדעתי אין כאן צורך בקלט נוסף
לדעתי הוכחה של טורינג לא דורשת קלט נוסף, למרות שהיא משתמשת בו.
אתה טוען שהאלגוריתם שלך פועל על *כל* האלגוריתמים הקיימים.
מבין אלה קיים האלגוריתם המתואר בהוכחה, אחרי הכל הוא אלגוריתם, זה שהוא משתמש באלגוריתם שהבאת לו זה לא קשור כי הוא היה קיים גם לפני שאתה הבאת את האלגוריתם שלך, בתור אחד מכל האלגוריתמים הקיימים.כותרת: איש חכם אחד אמר פעם…
בעצם נידמה לי שזה היה אני. מממ….
ש-
עדיף לא להתעסק עם שאלות שגורמות כאב ראש.
)))))))או לפחות לדעת לנחש תשובות.
עשיתם פסיכומטרי ?
איך היה ?ומיכאל, עוד רגע תגיד שהארץ מסתובבת סביב השמש, ולא להפך, ואז בכלל
ישימו אותך על מדורהכותרת: טכנית הארץ והשמש שניהם משפיעים על תנועת האחר,
השמש רק משפיעה הרבה יותר.(תחשוב על מערכת בינארית רק כשאחד הכוכבים רק הרבה יותר גדול)כותרת: re: halting problem, the easy part
There is a fine point here. No, the input is necessary, as I see it.
You see, if the input is not necessary you claim as follows:
You say you programmed an algorithm that determines whether the input algorithm halts. Well, I(it´s you, not me) disagree. I will program the function trouble( that, among others, call a function that determines if a algorithm halts) and it will confuse your algorithm. Wait – but you said it´s impossible to program such a function – how will you do that?BTW, I must admit i´m completely lost with this topic. But, Uri,
wait, I´ll find something, be sure. Actually I have some ideas already.כותרת: Earth-Sun
Influence and spinning around are two differnet things
Anyway, people, i´ve started a discussion about philosophy and you talk about some trivial Physics. Wake up, peopleכותרת: 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:
Ok… here´s something fishy about this:We assume function Halt does indeed exist, and set out to prove this results in a contradiction. What we know about the function is that it receives another function and its input as Halt´s input, and outputs whether or not the function halts. But, if this function exists, *it will always halt*, since it must return a result.
Now, let Halt(0) be the Halt iteration called from within Trouble and Halt(1) be the Halt testing Trouble.
What our Trouble function does is essentially reverse the output of the Halt function called from within Trouble. What Turing then claims is that if we feed the Trouble function back into Halt, we will get a wrong result in both cases. Let´s examine the two cases:
1) The initial function (F) is indeed infinite (won´t halt): F is fed into Halt(0), which returns "no", because it is infinite. Trouble in turn returns "yes", and hereby halts. Halt(1) returns "yes", because Trouble has halted. Turing claims this is wrong, because F hasn´t halted and therefore Halt is wrong. Here I disagree. Halt(1) was meant to test *Trouble*, *not* F. Halt(0) is finite by our assumption, and so Trouble is also finite, and Halt(1) is right. No contradiction!
2) The initial function (F) is finite. Halt(0) returns "yes", and so Trouble becomes infinite, and Halt(1) returns "no". Again, Halt(1) was meant to test Trouble, not F, and is therefore right. No contradiction again.
So, what am I missing here?
Oren
כותרת: זה ממש פסיכולוגיה מה שהולך פה
הקלט הכרחי להוכחה כמו שהוא הכרחי לכל הוכחה בשלילה. זה שהתוכנית שהביא טורינג משתמשת באלגוריתם הנתון לא משנה את העובדה שזו תוכנית לכל דבר.
אבל ההוכחה רק באה להוכיח שלא ניתן לפתור את בעית העצירה במקרה הכללי. לדעתי לא רק שלא ניתן לפתור אותה, אלא שעבור כל אלגוריתם שתביא יהיה ניתן למצוא אלגוריתם ספציפי יותר (אחד שלא ישתמש באלגוריתם שלך) עבורו האלגוריתם שלך לא נכון.
אם הבנתי אותך, זוהי הטענה שאתה מחפש, אבל נשמע לי קשה להוכיח את זה (אם זה נכון, מה שלדעתי כן)
בנוסף נשמע לי בעייתי להגדיר "אלגוריתם שלא משתמש באלגוריתם אחר"
אבל את זה נשאיר למטורף שינסה להוכיח את זה
- יש להתחבר למערכת על מנת להגיב.