Ένα ποίημα αφιερωμένο στο Halting Problem

Αναδημοσιεύσεις άρθρων και κειμένων που βρήκατε κάπου αλλού και θέλετε να μοιραστείτε μαζί μας .
Post Reply
The Punisher
Venus Former Team Member
Posts: 7561
Joined: Thu Oct 27, 2005 1:43 pm
Academic status: Alumnus/a
Gender:
Location: Boston, MA

Ένα ποίημα αφιερωμένο στο Halting Problem

Post by The Punisher » Sun Jun 21, 2009 3:26 pm

Το διάβασα σήμερα και ψιλο-έμεινα! Είναι πολύ καλογραμμένο, πολύ προσεγμένο, πολύ "up to the point" και λέει τα πράγματα όπως θα έπρεπε. Το παραθέτω για να το δείτε κι εσείς. Συγχαρητήρια στους δημιουργούς .. :smt023
No general procedure for bug checks succeeds.
Now, I won't just assert that, I'll show where it leads:
I will prove that although you might work till you drop,
you cannot tell if computation will stop.

For imagine we have a procedure called P
that for specified input permits you to see
whether specified source code, with all of its faults,
defines a routine that eventually halts.

You feed in your program, with suitable data,
and P gets to work, and a little while later
(in finite compute time) correctly infers
whether infinite looping behavior occurs.

If there will be no looping, then P prints out `Good.'
That means work on this input will halt, as it should.
But if it detects an unstoppable loop,
then P reports `Bad!' --- which means you're in the soup.

Well, the truth is that P cannot possibly be,
because if you wrote it and gave it to me,
I could use it to set up a logical bind
that would shatter your reason and scramble your mind.

Here's the trick that I'll use -- and it's simple to do.
I'll define a procedure, which I will call Q,
that will use P's predictions of halting success
to stir up a terrible logical mess.

For a specified program, say A, one supplies,
the first step of this program called Q I devise
is to find out from P what's the right thing to say
of the looping behavior of A run on A.

If P's answer is `Bad!', Q will suddenly stop.
But otherwise, Q will go back to the top,
and start off again, looping endlessly back,
till the universe dies and turns frozen and black.

And this program called Q wouldn't stay on the shelf;
I would ask it to forecast its run on itself.
When it reads its own source code, just what will it do?
What's the looping behavior of Q run on Q?

If P warns of infinite loops, Q will quit;
yet P is supposed to speak truly of it!
And if Q's going to quit, then P should say `Good'
--- which makes Q start to loop! (P denied that it would.)

No matter how P might perform, Q will scoop it:
Q uses P's output to make P look stupid.
Whatever P says, it cannot predict Q:
P is right when it's wrong, and is false when it's true!

I've created a paradox, neat as can be ---
and simply by using your putative P.
When you posited P you stepped into a snare;
Your assumption has led you right into my lair.

So where can this argument possibly go?
I don't have to tell you; I'm sure you must know.
By reductio, there cannot possibly be
a procedure that acts like the mythical P.

You can never find general mechanical means
for predicting the acts of computing machines.
It's something that cannot be done. So we users
must find our own bugs. Our computers are losers!

Original link
User avatar
enum21
Venus Former Team Member
Posts: 5436
Joined: Mon Feb 16, 2009 9:06 pm
Academic status: Alumnus/a
Gender:
Location: Underworld

Re: Ένα ποίημα αφιερωμένο στο Halting Problem

Post by enum21 » Sun Jun 21, 2009 3:58 pm

Είναι υπέροχο!!! :smt007 Πραγματικα!!! :razz:
Μπράβο σε αυτούς που το έγραψαν,έστω και αν είχαν πολύ δύσκολη δουλειά το αποτέλεσμα τα λέει όλα :)
jimm
Kilobyte level
Kilobyte level
Posts: 290
Joined: Sun Nov 16, 2008 11:16 pm
Gender:
Location: Wall St.

Re: Ένα ποίημα αφιερωμένο στο Halting Problem

Post by jimm » Mon Jul 13, 2009 7:30 am

Καποτε μου αρεσαν αυτου του στυλ τα ζητηματα, μεχρι που διαπιστωσα οτι η θεωρητικη πληροφορικη ειναι μια πλανη.
The Punisher
Venus Former Team Member
Posts: 7561
Joined: Thu Oct 27, 2005 1:43 pm
Academic status: Alumnus/a
Gender:
Location: Boston, MA

Re: Ένα ποίημα αφιερωμένο στο Halting Problem

Post by The Punisher » Mon Jul 13, 2009 10:12 am

Ok, πάνσοφε διανοητή :lol: , αφού το διαπίστωσες ..
jimm
Kilobyte level
Kilobyte level
Posts: 290
Joined: Sun Nov 16, 2008 11:16 pm
Gender:
Location: Wall St.

Re: Ένα ποίημα αφιερωμένο στο Halting Problem

Post by jimm » Mon Jul 13, 2009 7:03 pm

Κατα πρωτον απαιτω να φας ban γιατι μου κανεις προσωπικη επιθεση. :-D :-D
Επι του θεματος αμα το καλοσκεφτεις η θεωρ. πληροφορικη και η χρησιμοτητα της ειναι περιπου αναλογη με το να λυνεις σταυρολεξα, πλην ελαχιστων εξαιρεσεων.
Βρες μια χρησιμοτητα -πλην της διασκεδασης τυπου σταυρολεξο- του να κατατασεις πχ θεωρητικα προβληματα σε 100 διαφορετικες ταξεις δυσκολιας και πολυπλοκοτητας, τη στιγμη που ξερεις οτι ολα τους ειναι στην πραξη αλυτα. :cool:
Last edited by jimm on Mon Jul 13, 2009 7:13 pm, edited 1 time in total.
User avatar
stoupeace
Wow! Terabyte level
Wow! Terabyte level
Posts: 5372
Joined: Tue Aug 26, 2008 4:08 pm
Academic status: High school
Gender:

Re: Ένα ποίημα αφιερωμένο στο Halting Problem

Post by stoupeace » Mon Jul 13, 2009 7:12 pm

If scientists had your way of thinking, you wouldnt post anything here, cause this forum wouldnt exist, cause PC's wouldnt exist. Παρόλα αυτά έχεις ακόμα πλάκα, οπότε σε παρακαλώ πες κι άλλα!
Η καλύτερη μπάντα όλου του κόσμου: Sonata Antartika
Mpomp is building an army army. And I got my head back.
░░░░░███████ ]▄▄▄▄▄▄▄▄
▂▄▅█████████▅▄▃▂ ____☻/︻╦╤─
Il███████████████████]. /▌
_◥⊙▲⊙▲⊙▲⊙▲⊙▲⊙▲⊙◤.. . / \
jimm
Kilobyte level
Kilobyte level
Posts: 290
Joined: Sun Nov 16, 2008 11:16 pm
Gender:
Location: Wall St.

Re: Ένα ποίημα αφιερωμένο στο Halting Problem

Post by jimm » Mon Jul 13, 2009 7:14 pm

Stoupeace wrote:If scientists had your way of thinking, you wouldnt post anything here, cause this forum wouldnt exist, cause PC's wouldnt exist.
Κι αν καταλαβαινες τι λεμε, δε θα ησουνα off topic ;)
User avatar
stoupeace
Wow! Terabyte level
Wow! Terabyte level
Posts: 5372
Joined: Tue Aug 26, 2008 4:08 pm
Academic status: High school
Gender:

Re: Ένα ποίημα αφιερωμένο στο Halting Problem

Post by stoupeace » Mon Jul 13, 2009 7:19 pm

jimm wrote:
Stoupeace wrote:If scientists had your way of thinking, you wouldnt post anything here, cause this forum wouldnt exist, cause PC's wouldnt exist.
Κι αν καταλαβαινες τι λεμε, δε θα ησουνα off topic ;)
Eφυγα απο το halting problem, και σταθηκα στο οτι λες "Γιατί να ασχολούμαστε αφού είναι άλυτα". Γουτσούνι :-D
Η καλύτερη μπάντα όλου του κόσμου: Sonata Antartika
Mpomp is building an army army. And I got my head back.
░░░░░███████ ]▄▄▄▄▄▄▄▄
▂▄▅█████████▅▄▃▂ ____☻/︻╦╤─
Il███████████████████]. /▌
_◥⊙▲⊙▲⊙▲⊙▲⊙▲⊙▲⊙◤.. . / \
The Punisher
Venus Former Team Member
Posts: 7561
Joined: Thu Oct 27, 2005 1:43 pm
Academic status: Alumnus/a
Gender:
Location: Boston, MA

Re: Ένα ποίημα αφιερωμένο στο Halting Problem

Post by The Punisher » Mon Jul 13, 2009 9:47 pm

Κοίτα, σοβαρά τώρα, πραγματικά δε νομίζω ότι μπορώ να σε πείσω για το πόσο λάθος είσαι, οπότε δεν ξέρω αν έχει νόημα να κάθομαι να γράφω σεντόνια. Έχεις τις απόψεις σου, δεκτόν. Μην ισχυρίζεσαι όμως ότι κατέχεις και την "απόλυτη" αλήθεια, την οποία όλοι οι υπόλοιποι χαζούληδες δεν βλέπουν
User avatar
cyberpython
Mbyte level
Mbyte level
Posts: 654
Joined: Wed Nov 21, 2007 8:18 pm
Academic status: Alumnus/a
Gender:
Location: Αθηνα
Contact:

Re: Ένα ποίημα αφιερωμένο στο Halting Problem

Post by cyberpython » Mon Jul 13, 2009 10:38 pm

jimm wrote:Κατα πρωτον απαιτω να φας ban γιατι μου κανεις προσωπικη επιθεση. :-D :-D
Επι του θεματος αμα το καλοσκεφτεις η θεωρ. πληροφορικη και η χρησιμοτητα της ειναι περιπου αναλογη με το να λυνεις σταυρολεξα, πλην ελαχιστων εξαιρεσεων.
Βρες μια χρησιμοτητα -πλην της διασκεδασης τυπου σταυρολεξο- του να κατατασεις πχ θεωρητικα προβληματα σε 100 διαφορετικες ταξεις δυσκολιας και πολυπλοκοτητας, τη στιγμη που ξερεις οτι ολα τους ειναι στην πραξη αλυτα. :cool:
Για φαντάσου όμως κάποια στιγμή να βρεθεί τρόπος να λύνεται (σε λογικό χρόνο) ένα πρόβλημα μίας ομάδας - αυτόματα έχεις λύσει όλα τα άλλα προβλήματα που ανάγονται σε αυτό. Οπότε έχει νόημα - για την ακρίβεια όσο νόημα είχε η μέτρηση της απόστασης Γης-Σελήνης για τους αρχαίους μας προγόνους. Μπορεί να μην έχει πρακτική αξία αυτή τη στιγμή αλλά δε ξέρεις τι μπορεί να συμβεί αύριο.
jimm
Kilobyte level
Kilobyte level
Posts: 290
Joined: Sun Nov 16, 2008 11:16 pm
Gender:
Location: Wall St.

Re: Ένα ποίημα αφιερωμένο στο Halting Problem

Post by jimm » Tue Jul 14, 2009 1:25 am

The Punisher wrote:Κοίτα, σοβαρά τώρα, πραγματικά δε νομίζω ότι μπορώ να σε πείσω για το πόσο λάθος είσαι, οπότε δεν ξέρω αν έχει νόημα να κάθομαι να γράφω σεντόνια. Έχεις τις απόψεις σου, δεκτόν. Μην ισχυρίζεσαι όμως ότι κατέχεις και την "απόλυτη" αλήθεια, την οποία όλοι οι υπόλοιποι χαζούληδες δεν βλέπουν
Για να μη μπαινουμε σε λεπτομερειες, θα σε παραπεμψω στους τονους απο θεωρητικα papers που βγαινουν καθε χρονο απο λογης λογης παν/μια και το 95% ειναι πρακτικως αχρηστα.
Χαιρονται οι διδακτορικοι και οι καθηγητες τους, δε λεω, αλλα απο εκει και περα χρησιμοτητα στον πραγματικο κοσμο ελαχιστη. Τα περισσοτερα καταληγουν στο συρταρι αμεσως μολις τελειωσει η παρουσιαση τους σε καποιο συνεδριο.
cyberpython wrote: Για φαντάσου όμως κάποια στιγμή να βρεθεί τρόπος να λύνεται (σε λογικό χρόνο) ένα πρόβλημα μίας ομάδας - αυτόματα έχεις λύσει όλα τα άλλα προβλήματα που ανάγονται σε αυτό.
Θεωρητικα εχεις δικιο φυσικα, πρακτικα πολυ αμφιβαλλω ομως.
User avatar
Dreamcatcher
Kilobyte level
Kilobyte level
Posts: 406
Joined: Sat Sep 22, 2007 10:37 am
Academic status: 3rd year
Gender:

Re: Ένα ποίημα αφιερωμένο στο Halting Problem

Post by Dreamcatcher » Tue Jul 14, 2009 9:55 am

cyberpython wrote:
jimm wrote:Κατα πρωτον απαιτω να φας ban γιατι μου κανεις προσωπικη επιθεση. :-D :-D
Επι του θεματος αμα το καλοσκεφτεις η θεωρ. πληροφορικη και η χρησιμοτητα της ειναι περιπου αναλογη με το να λυνεις σταυρολεξα, πλην ελαχιστων εξαιρεσεων.
Βρες μια χρησιμοτητα -πλην της διασκεδασης τυπου σταυρολεξο- του να κατατασεις πχ θεωρητικα προβληματα σε 100 διαφορετικες ταξεις δυσκολιας και πολυπλοκοτητας, τη στιγμη που ξερεις οτι ολα τους ειναι στην πραξη αλυτα. :cool:
Για φαντάσου όμως κάποια στιγμή να βρεθεί τρόπος να λύνεται (σε λογικό χρόνο) ένα πρόβλημα μίας ομάδας - αυτόματα έχεις λύσει όλα τα άλλα προβλήματα που ανάγονται σε αυτό. Οπότε έχει νόημα - για την ακρίβεια όσο νόημα είχε η μέτρηση της απόστασης Γης-Σελήνης για τους αρχαίους μας προγόνους. Μπορεί να μην έχει πρακτική αξία αυτή τη στιγμή αλλά δε ξέρεις τι μπορεί να συμβεί αύριο.
[οφφ]
Συμφωνώ εξάλλου για να έχουμε ένα πρακτικό αποτέλεσμα σε όλες τις επιστήμες πρέπει να έχουμε κτίσει ένα άρτιο θεωρητικό υπόβαθρο στο οποίο πάντα ανατρέχουμε...βασικά είναι άμεσα συνδεδεμένα...σκέψου πχ να γράφεις java χωρίς το doc...( καλα και το doc δεν είναι απόλυτα θεωρητικό αλλά καταλαβαίνεις τί θέλω να πω )...και όταν το θεωρητικό υπόβαθρο δεν μας στηρίζει το πρακτικό κομμάτι είναι πολύ δύσκολο να φτάσεις στο τέλος του...[/οφφ]

Το ποίημα όντως είναι καλογραμμένο και δεν κουράζει... :-D :-D :-D πραγματικά πολύ καλή προσπάθεια...
Αν δεν πιστέψεις το Αδύνατο, δεν θα φτάσεις ποτέ στα οριά του το Δυνατό!!!

Dreamcatcher
User avatar
rose
Gbyte level
Gbyte level
Posts: 1921
Joined: Sun May 20, 2007 8:59 pm
Academic status: 4th year
Gender:

Re: Ένα ποίημα αφιερωμένο στο Halting Problem

Post by rose » Tue Jul 14, 2009 9:58 am

Για Np,
ειναι αρκετά σημαντικό να καταλάβουμε οτι οι αποτυχίες της επιστήμης μας - ως γενικότερη έννοια - ειναι επιτυχίες.
που θα πάει θα το δουμε...
User avatar
Dreamcatcher
Kilobyte level
Kilobyte level
Posts: 406
Joined: Sat Sep 22, 2007 10:37 am
Academic status: 3rd year
Gender:

Re: Ένα ποίημα αφιερωμένο στο Halting Problem

Post by Dreamcatcher » Tue Jul 14, 2009 10:08 am

rose wrote:Για Np,
ειναι αρκετά σημαντικό να καταλάβουμε οτι οι αποτυχίες της επιστήμης μας - ως γενικότερη έννοια - ειναι επιτυχίες.
Άλλο αυτό και σίγουρα τα λάθη ήταν πολύ χρήσιμα για την συνέχεια...εγώ απλά θέλω να επισημάνω ότι δεν μπορούμε να προχωρήσουμε "χωρίς την θεωρία στην πράξη" το θέτω πολύ πολύ γενικά...

@rose
Και πες και τίποτα για το ποίημα θα μας φάει ο punisher που είμαστε offtopic :-D
Αν δεν πιστέψεις το Αδύνατο, δεν θα φτάσεις ποτέ στα οριά του το Δυνατό!!!

Dreamcatcher
User avatar
rose
Gbyte level
Gbyte level
Posts: 1921
Joined: Sun May 20, 2007 8:59 pm
Academic status: 4th year
Gender:

Re: Ένα ποίημα αφιερωμένο στο Halting Problem

Post by rose » Tue Jul 14, 2009 10:18 am

Δεν μιλάω για λάθη, η γνώση μας στο τι μπορεί να υπολογιστεί - και το αντίθετο - ειναι το πιο σημαντικό πράγμα στην επιστήμη μας, τι αλλο να ζητήσει κανείς?
που θα πάει θα το δουμε...
User avatar
Dreamcatcher
Kilobyte level
Kilobyte level
Posts: 406
Joined: Sat Sep 22, 2007 10:37 am
Academic status: 3rd year
Gender:

Re: Ένα ποίημα αφιερωμένο στο Halting Problem

Post by Dreamcatcher » Tue Jul 14, 2009 10:20 am

Συμφωνώ...όντως είναι χρήσιμο να ξέρεις τα όρια της γνώσης σου και ακόμα πιο χρήσιμο να τα ορίζεις εσύ τα όρια αυτά... :smt023 :smt023
Αν δεν πιστέψεις το Αδύνατο, δεν θα φτάσεις ποτέ στα οριά του το Δυνατό!!!

Dreamcatcher
User avatar
tekgeorge
byte level
byte level
Posts: 126
Joined: Tue Oct 17, 2006 9:23 pm

Re: Ένα ποίημα αφιερωμένο στο Halting Problem

Post by tekgeorge » Tue Jul 14, 2009 11:38 pm

Δηλαδή το να βρίσκεις στα προβήματα καλήτερους χρόνους εκτέλεσης τους και λιγότερη χρήση χώρου ή και καλήτερους προσεγγιστικούς αλγόριθμους είναι θεωρητικό και πρακτικά άχρηστο??? Θα τρελαθούμε εδω μέσα...
Και στο κάτω-κάτω τα μαθηματικά, η φυσική κλπ δεν έχουν θεωρία??? (Θα τρελαθούμε εδω μέσα...)^2 :???:
User avatar
enum21
Venus Former Team Member
Posts: 5436
Joined: Mon Feb 16, 2009 9:06 pm
Academic status: Alumnus/a
Gender:
Location: Underworld

Re: Ένα ποίημα αφιερωμένο στο Halting Problem

Post by enum21 » Mon Nov 23, 2009 9:41 pm

Ανασταίνω αυτό το topic για να βάλω κι εγώ μερικά ποιηματάκια

Undecidability of the Halting Problem
To show the Halting Problem can't be algorithmically solved,
We use diagonalization, a proof method that's evolved
Where Turing Machines are asked to run in modes of simulation,
On codes that represent themselves, an auto-copulation.

Suppose a TM we'll call Halt, with input that's a code
Of another machine M, and in addition is showed
An input x to M, whence Halt says (and it's always right)
Whether M did halt on x. (But how? Divine insight?)

Let TM D, with input that's the code of machine A
Use Halt to find if A will halt on its own code, then say,
``If the answer's `no' I'll output 1, else fight the urge
To give another answer''-- better then that D diverge.

Rather than recount the proof's denouement, we'll be prudent,
And leave the rest to you, dear reader, the ever-able student.
When Halt is given the code of D, it simply cannot know
If D does halt on its own code--but that's for you to show.

The trick is to diagonalize--D changed the bit returned
By Halt, thus contradicts its work, as its output is spurned.
No matter how a TM solves the Halting Problem, see,
Diagonalization makes a counter-example. Q.E.D.
link

P and NP
If a Turing Machine were to guess,
With less computational stress,
Polynomially check
That its guess was not dreck,
Thus avoiding enumerative mess.

The machine would then certainly be
Witness to a language in NP.
By guessing, we shirk
Exponential-time work.
Nondeterminism can do search for free.

Cook and Levin, I am now recalling
Found a language L that's really galling:
If there is time compaction
To prove satisfaction
Then P=NP--appalling!

It is computational fate
To encounter such barriers we hate.
Yet there are computations
To find estimations
Within factors approximate.
link

and my favourite one :razz:
The Pumping Lemma
Any regular language L has a magic number p
And any long-enough word in L has the following property:
Amongst its first p symbols is a segment you can find
Whose repetition or omission leaves x amongst its kind.

So if you find a language L which fails this acid test,
And some long word you pump becomes distinct from all the rest,
By contradiction you have shown that language L is not
A regular guy, resiliant to the damage you have wrought.

But if, upon the other hand, x stays within its L,
Then either L is regular, or else you chose not well.
For w is xyz, and y cannot be null,
And y must come before p symbols have been read in full.

As mathematical postscript, an addendum to the wise:
The basic proof we outlined here does certainly generalize.
So there is a pumping lemma for all languages context-free,
Although we do not have the same for those that are r.e.
link

Congrats στους δημιουργούς!! :smt023
User avatar
para
Wow! Terabyte level
Wow! Terabyte level
Posts: 3648
Joined: Sat Nov 04, 2006 2:59 am
Academic status: Alumnus/a
Gender:

Re: Ένα ποίημα αφιερωμένο στο Halting Problem

Post by para » Mon Nov 23, 2009 10:57 pm

Μου θυμίζουν ένα ποιηματάκι που είχε γράψει ο cactus!! :-D :-D
Θυμάται κανείς;

edit: To βρήκα!!!

:smt005 :smt005 :smt005
Επικό!!!
:smt043 :smt043
Γύρνα είμαι ένα άψυχο κορμί που σ' αγαπάει, αισθάνομαι στον άνεμο φτερό
Σαν μέσα σε όνειρο η ζωή με προσπερνάει, δείξε μου οίκτο μια στιγμή παρακαλώ...
#!
Κοίτα πως με κατάντησε η δική σου η αγάπη, να μη γνωρίζω από που να κρατηθώ
Στο τελευταίο της ζωής το σκαλοπάτι, Γύρνα, είμαι ένα βήμα απ' το γκρεμό...
Post Reply

Return to “Αναδημοσιεύσεις”