Venus AUEB Forum

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!

Stoupeace wrote:If scientists had your way of thinking, you wouldnt post anything here, cause this forum wouldnt exist, cause PC's wouldnt exist.

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

jimm wrote:Κατα πρωτον απαιτω να φας ban γιατι μου κανεις προσωπικη επιθεση.
Επι του θεματος αμα το καλοσκεφτεις η θεωρ. πληροφορικη και η χρησιμοτητα της ειναι περιπου αναλογη με το να λυνεις σταυρολεξα, πλην ελαχιστων εξαιρεσεων.
Βρες μια χρησιμοτητα -πλην της διασκεδασης τυπου σταυρολεξο- του να κατατασεις πχ θεωρητικα προβληματα σε 100 διαφορετικες ταξεις δυσκολιας και πολυπλοκοτητας, τη στιγμη που ξερεις οτι ολα τους ειναι στην πραξη αλυτα.

The Punisher wrote:Κοίτα, σοβαρά τώρα, πραγματικά δε νομίζω ότι μπορώ να σε πείσω για το πόσο λάθος είσαι, οπότε δεν ξέρω αν έχει νόημα να κάθομαι να γράφω σεντόνια. Έχεις τις απόψεις σου, δεκτόν. Μην ισχυρίζεσαι όμως ότι κατέχεις και την "απόλυτη" αλήθεια, την οποία όλοι οι υπόλοιποι χαζούληδες δεν βλέπουν

cyberpython wrote: Για φαντάσου όμως κάποια στιγμή να βρεθεί τρόπος να λύνεται (σε λογικό χρόνο) ένα πρόβλημα μίας ομάδας - αυτόματα έχεις λύσει όλα τα άλλα προβλήματα που ανάγονται σε αυτό.

cyberpython wrote:

jimm wrote:Κατα πρωτον απαιτω να φας ban γιατι μου κανεις προσωπικη επιθεση.
Επι του θεματος αμα το καλοσκεφτεις η θεωρ. πληροφορικη και η χρησιμοτητα της ειναι περιπου αναλογη με το να λυνεις σταυρολεξα, πλην ελαχιστων εξαιρεσεων.
Βρες μια χρησιμοτητα -πλην της διασκεδασης τυπου σταυρολεξο- του να κατατασεις πχ θεωρητικα προβληματα σε 100 διαφορετικες ταξεις δυσκολιας και πολυπλοκοτητας, τη στιγμη που ξερεις οτι ολα τους ειναι στην πραξη αλυτα.

Για φαντάσου όμως κάποια στιγμή να βρεθεί τρόπος να λύνεται (σε λογικό χρόνο) ένα πρόβλημα μίας ομάδας - αυτόματα έχεις λύσει όλα τα άλλα προβλήματα που ανάγονται σε αυτό. Οπότε έχει νόημα - για την ακρίβεια όσο νόημα είχε η μέτρηση της απόστασης Γης-Σελήνης για τους αρχαίους μας προγόνους. Μπορεί να μην έχει πρακτική αξία αυτή τη στιγμή αλλά δε ξέρεις τι μπορεί να συμβεί αύριο.

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

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.

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.

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.