Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Can you pay someone to solve the halting problem?


I think we all agree that open source is not the holy grail but it shines with comparative advantages. It is like democracy: Far from perfect but still the best political system:

'Many forms of Government have been tried, and will be tried in this world of sin and woe. No one pretends that democracy is perfect or all-wise. Indeed it has been said that democracy is the worst form of Government except for all those other forms that have been tried from time to time.'

https://richardlangworth.com/worst-form-of-government

(OK, that was slightly OT!)




So the plutocrats will protect us from the majority? :)

Obviously we need constitutional rights and bureaucrats to implement the will of the people as expressed in the polls. But why do we need representatives? Do you really think eg a Tea Party representative will protect Muslims from the majority better than the first amendment and courts?


"So the plutocrats will protect us from the majority? :)"

No. The lesson, as usual, is that extremes rarely work out for us. The plutocrats will screw us if totally in control. So will politicians if they can get money from them or special interest groups. So will democracy if something horrible is trending in popularity. As usual, the solution will be a compromise between various points in the design space with more effective checks on various interactions and risks each pose to each other. I can't tell you what that design will be but looking for it is best investment with these things.

"Do you really think eg a Tea Party representative will protect Muslims from the majority better than the first amendment and courts?"

The First Amendment is subject to interpretation by representatives and/or courts. Fourth, Fifth, and Fourteenth have seriously been watered down. They're among the best examples of the risk. A politician can outlast the media fervor of the moment, get advise from well-informed people, and have teams check the side effects of the law. The current situation exists because apathetic democracy allows them to get away with not doing that. Also, passing laws in exchange for bribes. That could all be stopped with enough voter action followed by legislation or alternative models. The benefits of representational democracy remain.

I'm not saying I believe it's the best system. I'm just saying plutocrats and mobs cause lots of problems it can prevent with less effort than constantly outsmarting plutocrats or fighting mobs. So, it's a consideration.


The current situation exists because apathetic democracy allows them to get away with not doing that. Also, passing laws in exchange for bribes.

Or it exists because it is an emergent phenomenon that arises eventually. An increasingly polarized two-party system where each primary race is rigged against outsiders and voters are scared to vote third-party because each candidate is super scary to the opposing party. It's bound to happen eventually. In this case it happened in the US presidential race. And Congress has long had a 10% approval rating. One can make up reasons as to why it happened or accept that a representative democracy eventually reaches such states, and it's not clear how to get out of them with more representative democracy. Trying the same thing and expecting a different result.

I'm not saying I believe it's the best system.

Exactly, and I'm saying it's not. It's easier to fool all of the people some of the time (eg during elections) or heavily influence some the people all of the time (as lobbyists for special interests do) but you can't fool all the people all the time. That is far more expensive.

Once again ask yourself: are eg Muslim and Mexican US citizens safer if Donald Trump gets elected and magnifies the desire of those who elected him, or if the population at large was polled for policy? Are the people of Gaza better off under Hamas because they were democratically elected once by those who showed up? Would the Nazis ever get into power if there were no representative positions to get into? Besides gerrymandering, poor voter turnout and other major problems, representative democracy eventually gives a giant hammer to some special interest or other.

The crowd would do a better job on predicting policy outcomes than experts: http://www.npr.org/sections/parallels/2014/04/02/297839429/-...


I'm going to have to think on these points some more. :)


No, but neither can anyone else.

I can't proof that the neutral network always behaves correctly, but with testing and statistics you can verify the network up to a chosen certainty (below 100% obviously). Or you can actively search for problems with fuzzing techniques. All without solving the halting problem.


Right, but with the code in the open, it's easier to find ONE easy hole than to patch ALL the easy holes.


No that's not really how ANN's work.


ANNs?


artificial neural networks, you won't really be able to opening the code won't tell you much if anything, it's simply beyond the human capability to review.

So you'll end up with ANN's reviewing other ANN's which are reviewed by other ANN's at the end.

You can test ANN's by simply fuzzing them and seeing the output, getting much insight to why an outcome was chosen for a given data set is near impossible.


Lots of ways to review them:

https://people.cs.umass.edu/~btaylor/publications/PSI000008....

These are also just the first steps. Not bad given what hardware and software verification used to look like a few decades ago. I think the verifiable ANN's will be more structured or constrained in their development or even use cases.


Have you actually read what the paper you've linked? I haven't said that it's impossible to review ANN's, but you do not need to review their code to do it, infact reviewing their code is the wrong approach in this case. You do not want to be conducting code inspection on nondeterministic systems as it would yield very little. This means that having the ANN being open sourced does not add additional security by having the code inspectable by everyone like with traditional software. This is what the whole argument is about, not about can ANN's be reviewed.


You said:

"it's simply beyond the human capability to review. So you'll end up with ANN's reviewing other ANN's which are reviewed by other ANN's at the end."

That implied it was beyond human capability to review ANN's to the point we'd need ANN's to do it. In the paper, they give a number of deterministic methods to review ANN's noting some were successful by the teams using them. Countered both of your claims in that context.

"This means that having the ANN being open sourced does not add additional security by having the code inspectable by everyone like with traditional software."

I agree that most of the problems won't be caught here. More about training set and safety monitors. However, the paper shows methods like rule extraction, visualization, and simulation that have aided in assessing and improving neural networks. These work on that internal state that's incomprehinsible at first glance. It's also usually stored in HW logic, the SW code, or some data format. Having those provably facilitates analysis of ANN's performance. Assuming it's the kind that's analyzable at all. ;)

Note: Code-level errors, either by hand-written or auto-generated engines, can also invalidate an ANN's behavior. Vast majority of software flaws occur right here. Obviously, some static analysis or safety transformations can increase assurance of correctness of overall system. Should be combined with other V&V methods.


The full sentence was "...opening the code won't tell you much if anything, it's simply beyond the human capability to review." It was within a comment subthread about the value of traditional code inspections for reviewing ANN's more specifically will the availability of the code for everyone to inspect be as "valuable" for security assurance as traditional software, context is everything.

If you get a the source code of any traditional software reviewing the code can be done by humans regardless of how complex it is, with ANN's it's not really the case simply because of the nondeterministic nature of the system. You can validate the "correctness" of an ANN but it's not done in the same manner as reviewing traditional software.


"with ANN's it's not really the case simply because of the nondeterministic nature of the system. You can validate the "correctness" of an ANN but it's not done in the same manner as reviewing traditional software."

You have to do both: validate the non-deterministic aspects of the ANN logic and validate its implementation as code. Makes them a lot harder. One reason I avoid them.


I made money doing it one time. They told me I couldn't prove an arbitrary program would halt. I wrote a program that loaded an arbitrary algorithm into a process, counted down to zero from starting constant, attempted to kill the process when at zero, and otherwise shut down the whole system. "sklogic" similarly showed how pointless the question was when he said he could just put a while loop around any algorithm doing basically the same thing within the program.

So, not only can you prove a program halts using a verified halter, the techniques for doing so have prevented and detected many real-world problems. One of those situations where abstract math ignores simple, concrete solutions. :)


No, but for any given program I may be able to hire someone to tell me whether it halts.

Safety critical automotive software is going to tend to be an easier case, since it's quite likely to be extremely time bounded.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: