Page 1 of 3 123 LastLast
Results 1 to 10 of 21

Thread: Programming Problems

  1. #1

    Programming Problems

    Ok, I am reading a book, and low and behold, I come to a part, that starts to talk about problems, that a computer can't answer. For those of you that have an Idea, I am referring to the Halting Problem right now, my next question, are what other problems can't a computer answer, given unlimited resources, and unlimited Memory, what things, can I already not think about coding, because there is no way in hell it will work.

  2. #2
    AntiOnline n00b
    Join Date
    Feb 2004
    Posts
    666
    hi whizkid2300

    You are talking about unsolvable Problems..........I wouldn't be of much help to you because like you i too am going through such book.....actually it is in our school curriculum....compiler design.........i can state some unsolvable problems that i am familear of....... if you want to know .....

    First i think you are familear of Turing Machine are you? .........First problem is as you stated the Halting Problem(or the halting Problem of a Turing Machine)

    2. The Thue System : the word problem of Thue system is unsolvable

    3. Post Correspondance Problem

    4. The Unsolvable Tiling Problem

    are a few that come to my mind just now......if you want i will look into and give you an explanation.....of the above...but the book that has the Halting Problem must also have described the above said problems too....

    As i said i am not being much help to you as i too am trying to get a grip of them myself

    --Good Luck---

  3. #3
    Well, there are i few things i can come up with:

    try writing a program which can convert an executable into good readable C source code. (and i'm not talking about missing var names) but the real stuff.

    write a program, which writes programs for you.
    (without limitations).

    try writing a program which can read a complete OS, and tell where there might be vulnerabilities like bufferoverflows possible ( detect the ones that aren't known yet).



    if you can write any of these programs, then don't bother getting a job, cause i think you will make so much money with it , you don't need a job for the rest of your life

  4. #4
    lepricaun, don't take this wrong, but do you have any idea what your talking about?

    The area, that I am talking about, are things, that computers actually can't solve for many different reasons, the things that you listed, are things that haven't been done though they can.

    The thing, I am referring to are things, that can't be done.

    Oh and a program that writes programs for you. Ugh... ever hear of VB?

    It is kind of hard to explain. I will explain it better later.

  5. #5
    A program that calculates the exact value of pi. =P

    Good luck,
    - dave

  6. #6
    A program that calculates the exact value of pi. =P
    Ugh... no, the point of what I am referring to are things, that can't be done. Even with infinite time, and infinite resources. Though Pi, always goes on, you can still keep going. A program can be written to keep creating every number of pi, and keep going and keep going. It won't ever get to the end, but it will keep going. The things, I am referring to are things, that can't be done.

    Let me explain better.

    Look at this link

    http://en.wikipedia.org/wiki/Halting_problem

    That can't be done by a computer.

  7. #7
    AntiOnline n00b
    Join Date
    Feb 2004
    Posts
    666
    Hi

    Yep and washing my dirty socks is also a Unslovable Problem


    The problem you Guys are talking about can be solved if we put in sufficient recources...

    Unsolvable Problems are a bit Different....I will give you a hint........Like for example Lets Consider The Halting Problem....... The Halting Problem is about an abstract computer that runs forever....has infinite UpTime.......... and has no limit on memory..........memory can vary no matter how much you need (increase or decrease at any point)............. It can even keep asking for another writing disk(hard Disk or whatever media used) and can ask to read and write on any disk it previously used..............Even with the use of such a Computer these problems can't be solved..........There is no alogrithinm to solve these problems


    Imagine a Computer like that ........... in the middle of the night it asks you wke up i need another RAM stick and oo don't forget a extra Disk too


    To understand these you will have to know what a Turing Machine is.........what is a Contaxt free Grammer.......what is a context free language ........what is a turing accaptable languages.......etc. etc.

    Because the Proper Defination of the Halting Problem is : A computational problem that cannot be solved by a Turing machine.


    For Further Info i would recommed you try out any book on Theory of Computation

    --Good Luck--

    [edit] Ok whizkid2300 Beat me to it ...Post wasen't there when i started typing mine


    [Edit 2] Just realised with this post i am a Senior Memeber Now............... and that means i just lost my Addiction

  8. #8
    ok now i see, i can think of one problem which I can't solve, and i think no one else can too:


    program A.exe

    md5 sum A.exe --> AB495DFE8929572017BA01 (not a correct one but that doesn't matter).

    now take the md5sum of the program and use it in the program to see if it has been altered. but as soon as you do this, the md5sum will change and therefore the program will not work. this is an infinite problem, just like the question:

    what came first, the chicken or the egg?

    i know this isn't really what you ask, but i'm not a programming student to learn all that kind of (IMHO useless) things, i just learn programming myself


    [edit]p.s. i believe every problem will eventually be solved, just like A.I. will become more stronger and smarter in time[/edit]

  9. #9
    You will be surprised, how something that you think is Unimportant, can become important.

    I have already ran into the halting problem which is why I started reading the book I am reading.

    It always amazes me how the things, that I think I don't want to know and think I won't ever need to know, always become the things, that I need to know best.


    Ugh... Lepricaun. I am thinking a pointer, might be able to do that.

  10. #10
    AntiOnline n00b
    Join Date
    Feb 2004
    Posts
    666
    hi

    i know this isn't really what you ask, but i'm not a programming student to learn all that kind of (IMHO useless) things, i just learn programming myself
    lepricaun it depends.................For someone who codes things like Device Drivers and Compilers.........these very useless things becomes of utter Importance ..........so don't say that these are useless ...........for you probably yes ( But i doubt that .............a coder will someday bump into them you can run but you can't hide Muhahahah )..

    btw WizKid~ i don't know which book you are refering to ......but if you want to get the mathematical aspect of these problems i would suggest Elements of The Theory of Computation --By Harry R. Lewis thats what i am refering to these days .

    --Good Luck--

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •