Programming Problems

[whizkid2300]

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.

[SwordFish_13]

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---

[lepricaun]

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 :D

[whizkid2300]

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.

[God's Whore]

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

Good luck,
- dave

[whizkid2300]

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.

[SwordFish_13]

Hi

Yep and washing my dirty socks is also a Unslovable Problem :p


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 :p


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 :(

[lepricaun]

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 :)


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

[whizkid2300]

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.

[SwordFish_13]

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--

[lepricaun]

well, perhaps i might need it in the future, but for now i'm sure i don't need them.
but maybe i wouldn't even noticed when i ran into it, it all depends :D

[SerpentSin]

[i]
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 :)


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

Well, if these theories were useless, you wouldn´t be sitting on your machine reading this message right now, you wouldn´t even have a subject called programming. Computers need solid sets of rules to work on, not fuzzy speculations. Saying this type of knowledge is useless would be the same as being an architect that says bricks are useless, just cause he doesn´t mess with bricks directly, but he´ll eventually need bricks to build the buildings he designs.

[lepricaun]

Well, if these theories were useless, you wouldn´t be sitting on your machine reading this message right now, you wouldn´t even have a subject called programming. Computers need solid sets of rules to work on, not fuzzy speculations. Saying this type of knowledge is useless would be the same as being an architect that says bricks are useless, just cause he doesn´t mess with bricks directly, but he´ll eventually need bricks to build the buildings he designs i don't think you get my point, of course programming would need a set of rules, but it is also true that the restrictions of a language might not apply to another language, and if you want to write a program you'll have to think how it should work, and i don't think about things that might not be able to solve, but i think in ways that the language i use WILL be able to work with it..

and problems that are impossible to solve for a computer, but not for a human being, this is what whizkid2300 meant, i know this, but like i said, eventually this problems will get solved since AI is getting more stronger every day....

[SerpentSin]

The subject of the post isn´t programming languages, it´s about programming problems and Theory of Computation. AI isn´t getting better, it´s just growing larger. With the type of computer logic we have today, it´ll be impossible to build anything near intelligence. The AI your talking about is a big database of predefined instructions that the computer uses to analyse different situations and that grows larger every day, eventualy a situation will arise that the database doesn´t provide any answers for and then your "AI" becomes just as dumb as an earthworm and whoever built the database will have to re-implement the program´s "Inteligence" as to adapt to the new situation.

[SwordFish_13]

hi lepricaun


Ok now i think whizkid2300 has abandoned this thread so i will hyjack it......sorry for that :)


I don't think you are getting the point.........the thing is we are not talking about programming languages and their rules or restrictions.............that has nothing to do with solving these problems.........absolutly NOTHING............we are talking good old Mathematics .......the name of the subject is Theory of Computation...........Computer is not the only thing that can compute we humans also can do that a bit slower but we still can.............and these problems are not computable with the current mathematical knowledge .

Algrothinms have been here long before Computer existed...........and there is no know algorithm to solve these problems,.....so it would need more ofa mthematician not a computer programmer to solve it ;)

now you are mixing those two things ...........you are just looking computer in a logical sence...........every thing that you do and see on these things still boil down to mathematics.

Now you said something about Programming language and rules and restrictions that it have..............now how does it do it..........how does it recognise it's syntax..............Every language has a grammer now what is a grammer (set of rules ) .........in mahtematical tearms a grammer would be a quadratuple G =(V, A,R,S) where

V is an alphabet

A is a subset of V is a terminal symbols and V-A is called the set of non terminal symbols;

S belongs to V - A is the start symbol

R , is the set of rules is a finite subset os ( V*(V-A*) X V*.

and so on so forth everything has a mathematical notion............the purpose of stating all this is to tell you the things you said were useless are indeed useful to somebody........they are the building block of everything here........now if a person who writes a compiler is not famalier with these terams he wouldn't be able to write it............this discussion is more mathematical than computer related..........this has nothing to do with a particular programming language but the basic building blocks of it........and thats what Theory of Computation deals with .


a but like i said, eventually this problems will get solved since AI is getting more stronger every day....

I hope you know what AI is.........not the defiantion but how it works how does it processas information............It just uses stored information and puts that information through various mathematical functions to get to the answer...............here again it's good old mathematical functions ( conjunction and disjunction and many other )...............as SerpentSin said you can increase the database and make it look like more intelligent......of course new things have been introduced like probabilistic Reasoning, heuristic Reasoning, object Oriented AI etc. ...............but still it needs stored information.........like probabilistic Reasoning is nothing but replacing the old data..........like we found out the old stored knowledge was not correct replace it with the new knowledge in the database......it's like i tried the knowledge in the database a given times say 5 and found it fails every time so i looked for the new knowledge and update my database accordingly...............looks more intelligent isen't it. :)

i hope i made my point clear

--Good Luck--

[lepricaun]

well , i learned something new about the Theory of Computation :D, sorry if i misunderstood, although i still think it is going about problems not solvable by computers (mathmetical) but easily solvable by humans...


p.s. how does the human mind work? aren't we just thinking about things due to our memory? meaning, doesn't this look very similar to a computer? we just add one memory to another to create new things, all this could be pre-programmed as a matter of speaking....

only difference, we have an instinct, but for the rest, everything could be written as a program, even the learning part....

http://www.jair.org/

[SerpentSin]

No, the human mind cannot be written as a program, not with the programming tools available until now. Besides instincts, we have something called "reason", and I wont go into that because it isn´t in the scope of the thread. Computers learn because they were instructed to, we are not obliged to learn, yet learning is something the mind can´t avoid. The truth is, no one knows how the human mind works, and maybe that´s why it can´t be simulated as a computer program. All we know, experimentally, is that it works very different than a computer. Humans don´t really compute, they reason, they simulate computing through reasoning and I guess thats why we cant compute as fast as a computer, because every time we execute something simple like 2 + 2 = 4, even if unconsciously, we go through the entire process of reasoning all over again why these two numbers added up will give us that specific result.

A perfect example of humans vs computers would be the Deep Blue x Kasparov chess event. Deep blue had a big database of every single grandmaster chess game played on the planet and it could mathematically analyse a few billion plays per second based on this database. Kasparov had a lifetime of chess experience and his reasoning. While deep blue would run over billions of plays per second, 90% of these were obviously bad moves and Kasparov would never even think of them, but Deep Blue would keep considering them over and over. In every match, Kasparov would play weird opening moves as to avoid imitating a game already present in deep blues´ database, to force deep blue to start "thinking", he would then later transpose the game to a well known pattern that he already was familiar with, while deep blue would have to start his O(n²) complexity algorithm to find a good move. He crafted this weapon against deep blue right there on the spot, no one taught him. That, my friends, is called Intelligence.

[lepricaun]

ok, i give up, you guys made your point, perhaps i'm just way ahead of things.... ;-) but i still believe eventually they can recreate the human mind...

as for the Theory of computation, i did get it wrong then, well then i'm just messing up this thread for no reason :(, i hope whizkid2300 will still get the correct answer to his question then.....

sorry dudes.....

[SerpentSin]

Here´s a good link about programming problems, a few of them, unsolvable

http://www.nist.gov/dads/termsType.html#P

edit: "programming programs?" that was terrible, sorry, fixed it now :)

[whizkid2300]

Lepricaun, don't take this the wrong way, but I didn't really pay much attention to your answers, I knew the area of how the answers I was looking for should look. So when I saw yours, I just dismissed it, as either you were talking out of your ass, or you didn't know what you were talking about, or didn't understand the question.

In anyway Thanks to you guys, for trying to explain it, I will definately say that SwordFish_13 explained it best, and I will be looking into it more.

Though, Thanks Serpentin, that last link was ****ing awesome.

[lepricaun]

Lepricaun, don't take this the wrong way, but I didn't really pay much attention to your answers, I knew the area of how the answers I was looking for should look. So when I saw yours, I just dismissed it, as either you were talking out of your ass, or you didn't know what you were talking about, or didn't understand the question. let's keep it to the last :D... well sorry bout that, i will check the links given to you too, since i want to know for i start mangling in someones topic without a right answer for the future :)