Like Tree1Likes
  • 1 Post By Perspective

Simple undecidable problems

This is a discussion on Simple undecidable problems within the General Discussions forums, part of the Community Boards category; Hi, Recently i have been studying about undecidability. And along with this study i saw many examples that involved really ...

  1. #1
    Registered User
    Join Date
    Oct 2005
    Location
    Brasil
    Posts
    220

    Simple undecidable problems

    Hi,

    Recently i have been studying about undecidability. And along with this study i saw many examples that involved really complex undecidable problems. And i saw too examples too much far from a concrete idea, like that of the halting problem of the Turing machines.

    So, does anyone know a simple example of a undecidable problem and a reference for that problem?

    Thank you.

  2. #2
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,412
    It would be best if you told us what are the ones you already saw examples for. Otherwise we'll probably be throwing in here problems that you know about already.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  3. #3
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    Salem likes this.

  4. #4
    Unregistered User Yarin's Avatar
    Join Date
    Jul 2007
    Posts
    1,597
    Heh. I was just reading up on the halting problem, and I have to say I disagree with the consensus. I read the wiki article, but as usual, it expects the reader to be a little more familiar with the topic than I am. So I found this one: The Halting Problem

    The idea is that it's "unsolvable", but that's not actually true. From what I read, I see no reason that the algorithm couldn't be written to be aware of said infinite recursions. In said case, I imagine a third response would be appropriate, e.g., "paradox" rather than "halts" or "loops". Because the algorithm _knows_ it's input -> output doesn't match a simple yes/no, does _not_ mean it doesn't know the answer. If you want to be a stickler about it, and say it _has_ to be yes/no, then that's fine, the answer would be, it loops. Because, it _is_ looping, just outside of the algorithm, rather than in it.

    I'm not say there aren't any "undecidable problems", just that the halting problem is a really weak example.

  5. #5
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    The problem states that it is impossible to determine if P halts for an arbitrary P. How does introducing the answer "I don't know" (which is what your "paradox" is) change that? In the formulation of your link, H gives the wrong answer for K. You propose that H instead should give no answer - but you haven't solved the problem.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  6. #6
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,169
    From what I read, I see no reason that the algorithm couldn't be written to be aware of said infinite recursions.
    O_o

    How? (Keep in mind, we are talking any "P" and any "I". It is easily done for specific "P" and specific "I".) If you've actually solved that, you've gone along way in solving every undecidable problem and trashed all of information theory.

    Soma

  7. #7
    Unregistered User Yarin's Avatar
    Join Date
    Jul 2007
    Posts
    1,597
    Quote Originally Posted by CornedBee View Post
    The problem states that it is impossible to determine if P halts for an arbitrary P. How does introducing the answer "I don't know" (which is what your "paradox" is) change that? In the formulation of your link, H gives the wrong answer for K. You propose that H instead should give no answer - but you haven't solved the problem.
    "I don't know" != "paradox". The paradox is that a boolean value simply _can't_ be returned, the very algorithm prevents it. There are certain ways of dealing with it in an accepting way.

    But... the reason I think the above reasoning isn't even necessary in the first place is because:
    The algorithm is infinity recursive (correct me if I wrong). P = K. K calls H, which calls K again, only, with an inverted I. A logical loop is entered, because P causes H to continue to ask itself for a contradictory answer. When processing an infinite logical loop, I don't see how it's not safe to say, that it never finishes, i.e., "false, it loops". (_even_ in a computationally quantum environment)

    Quote Originally Posted by phantomotap View Post
    How? (Keep in mind, we are talking any "P" and any "I". It is easily done for specific "P" and specific "I".) If you've actually solved that, you've gone along way in solving every undecidable problem and trashed all of information theory.
    I'm not following. What's the relevance of P being "any" or "specific"?

    Still on topic (though not dealing with the halting problem anymore), here's a good example of an "undecidable" problem:
    (% being modulo)

    400 % 0xFF = 145
    ∞ % 0xFF = ?


  8. #8
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,412
    Quote Originally Posted by Yarin View Post
    I'm not following. What's the relevance of P being "any" or "specific"?
    If P is self-aware (let's call it P1), you defined a specific "P". But the halting problem exists for "any" P, not just P of the type P1.

    All you proved is that the halting problem does not exist for P1. But that isn't the formulation of the problem.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  9. #9
    Unregistered User Yarin's Avatar
    Join Date
    Jul 2007
    Posts
    1,597
    Quote Originally Posted by Mario F. View Post
    If P is self-aware (let's call it P1), you defined a specific "P". But the halting problem exists for "any" P, not just P of the type P1.

    All you proved is that the halting problem does not exist for P1. But that isn't the formulation of the problem.
    I didn't think that was the point of the problem, but I see your points nonetheless.
    I'm not sure how one would go about testing "normal" algorithms in the first place, so I guess there's not much I can say about that altogether

  10. #10
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,412
    Quote Originally Posted by Yarin View Post
    I didn't think that was the point of the problem, but I see your points nonetheless.
    It's not my point. It's how the problem is described.

    Quote Originally Posted by Yarin View Post
    I'm not sure how one would go about testing "normal" algorithms in the first place, so I guess there's not much I can say about that altogether
    You can't test the halting problem using technology. Not until we can build a turing machine. Our current computers will throw one form or another of a stack overflow sometime during the loop. However, the problem is real and can can be demonstrated with the help of mathematics which, as you know, can go far beyond our technological limitations. And with mathematics it was also proved to be undecidable. So I agree, there is really not much you can say about it

    In any case the halting problem poses a serious threat to any attempts at creating a turing machine: It can either be used as a demonstration of why a turing machine can never be built, or be used to demonstrate why a turing machine would be technologically useless to us.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. simple chatbot problems
    By Whyrusleeping in forum C++ Programming
    Replies: 2
    Last Post: 06-09-2011, 01:04 PM
  2. Few simple problems
    By Crashie in forum C++ Programming
    Replies: 4
    Last Post: 12-22-2009, 12:41 PM
  3. problems w/my simple function
    By generalt in forum C Programming
    Replies: 9
    Last Post: 05-08-2009, 10:45 AM
  4. simple class, any problems?
    By Syneris in forum C++ Programming
    Replies: 6
    Last Post: 04-05-2002, 11:18 AM
  5. Simple Server problems...
    By Unregistered in forum C++ Programming
    Replies: 0
    Last Post: 10-20-2001, 08:51 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21