Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Solve the halting problem, $300-$1000

getacoder.com

Post reply on HN
Print view View original

11–20 of 86 posts

Re: Solve the halting problem, $300-$1000

#11

Post by amix »

The thing to note about the halting problem is that it's impossible to create a general solution that works for all the input programs. That said, one could create an approximative solution and even solve the halting problem for non-turning complete languages.

A lot of the time when we actually solve "hard" problems, we only find approximative solutions (this is for example true when doing static code analysis). Asking does program X have any non-trivial property G is impossible to do in the general case, so we find an approximative solution that can answer this in most of the cases.

Re: Solve the halting problem, $300-$1000

#12

Post by swombat »

tdavis wrote: post #10
swombat wrote: post #4

This is a good demonstration of why you should only outsource things that you could do yourself but don't have the time to do. Never outsource something you don't know how to do (at least not if it's a core competitive requirement).

One time I outsourced the creation of a simple Wordpress template which I didn't have time to do. I paid $300. Despite being given a pre-cut Photoshop file, the people could not figure out simple CSS bugs or even create the CSS necessary for the tabs. I spent more time managing them (aka teaching ) than it would have taken me to do it, in the end I had to do half of it anyway and this entire sick ordeal took nearly t…

That's a good point... I wouldn't consider it wise to try and outsource any complicated technology development to India/Pakistan/etc. However, I would consider doing so to an onshore firm that demonstrates to me that they have a clue. For instance, I know plenty of people who take on consulting work and could deal with your CSS without any problems. Depending on how much work was involved, they might even have been able to do it within $300.

Re: Solve the halting problem, $300-$1000

#13

Post by markessien »

Unfortunately, the person who put up the project did not specify that the solution has to complete within a timespan. So given a piece of code, a proposed solution could just try all possible values, trying to discover if it will halt. This may take very long.

If the project client complains, he will need to prove that your solution is wrong, and he cannot prove that if he does not give your solution enough time to try all possible combinations.

Re: Solve the halting problem, $300-$1000

#14

Post by Freaky »

amix wrote: post #11

The thing to note about the halting problem is that it's impossible to create a general solution that works for all the input programs. That said, one could create an approximative solution and even solve the halting problem for non-turning complete languages. A lot of the time when we actually solve "hard" problems, we only find approximative solutions (this is for example true when doing static code analysis). Aski…

http://research.microsoft.com/Terminator/

The ultimate goal of the TERMINATOR project is develop automatic techniques (and tools that implement them) that will allow us to prove that industrial software components cannot hang.

Re: Solve the halting problem, $300-$1000

#15

Post by [deleted] »

Freaky wrote: post #14
amix wrote: post #11

The thing to note about the halting problem is that it's impossible to create a general solution that works for all the input programs. That said, one could create an approximative solution and even solve the halting problem for non-turning complete languages. A lot of the time when we actually solve "hard" problems, we only find approximative solutions (this is for example true when doing static code analysis). Aski…

http://research.microsoft.com/Terminator/ The ultimate goal of the TERMINATOR project is develop automatic techniques (and tools that implement them) that will allow us to prove that industrial software components cannot hang.

[deleted]

Re: Solve the halting problem, $300-$1000

#16

Post by cabalamat »

Freaky wrote: post #14
amix wrote: post #11

The thing to note about the halting problem is that it's impossible to create a general solution that works for all the input programs. That said, one could create an approximative solution and even solve the halting problem for non-turning complete languages. A lot of the time when we actually solve "hard" problems, we only find approximative solutions (this is for example true when doing static code analysis). Aski…

http://research.microsoft.com/Terminator/ The ultimate goal of the TERMINATOR project is develop automatic techniques (and tools that implement them) that will allow us to prove that industrial software components cannot hang.

(Said in an Austrian accent:) They'll be back.

Re: Solve the halting problem, $300-$1000

#17

Post by alecco »

swombat wrote: post #12
tdavis wrote: post #10

Earlier quoted context omitted.

One time I outsourced the creation of a simple Wordpress template which I didn't have time to do. I paid $300. Despite being given a pre-cut Photoshop file, the people could not figure out simple CSS bugs or even create the CSS necessary for the tabs. I spent more time managing them (aka teaching ) than it would have taken me to do it, in the end I had to do half of it anyway and this entire sick ordeal took nearly t…

That's a good point... I wouldn't consider it wise to try and outsource any complicated technology development to India/Pakistan/etc. However, I would consider doing so to an onshore firm that demonstrates to me that they have a clue. For instance, I know plenty of people who take on consulting work and could deal with your CSS without any problems. Depending on how much work was involved, they might even have been a…

Outsourcing to a far away place to a random contractor is looking for trouble. But your generalization is offensive.

Re: Solve the halting problem, $300-$1000

#18

Post by marvin »

Freaky wrote: post #14
amix wrote: post #11

The thing to note about the halting problem is that it's impossible to create a general solution that works for all the input programs. That said, one could create an approximative solution and even solve the halting problem for non-turning complete languages. A lot of the time when we actually solve "hard" problems, we only find approximative solutions (this is for example true when doing static code analysis). Aski…

http://research.microsoft.com/Terminator/ The ultimate goal of the TERMINATOR project is develop automatic techniques (and tools that implement them) that will allow us to prove that industrial software components cannot hang.

This is actually pretty interesting. They aren't claiming that they are trying to make a general solution, just one that works in most cases. It might even be possible, AFAIK there hasn't been very much research in this area.
Post reply on HN