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

I'm not a computer scientist, but I am aware Interesting doesn't mean interesting to humans.

> And I'm talking about the decider

EDIT: If by decider you mean program tested for having property P, that's a particular case and not applicable in general, ergo non-important (a program that's a NOP can be shown to leak no memory as well).

So the property P you are testing always returns true? Then it's not interesting per your definition. Leaking memory however is interesting.



No that's not what I mean by decider. The decider is the program that takes the other program as input and tells you whether that input program has the semantic property you want.

The only noninteresting semantic properties of programs that exist are "this is a program" and "this is not a program."


Yes. And you said

> A program that emits "Yes" on every input will decide some property of programs with zero false negatives.

Followed by

> any semantic property that is not either always true or always false for all program executions

So what you said is your decider always outputs true. That's not an interesting property, because it's true for all inputs.

Btw what is the point of your argument? It still doesn't refute my initial statement. If you want to determine an interesting property of program like leaks, or automatic lifetime calculation or whether output is square of input, you run into Rice Theorem, which makes the problem undecidable. In other words it's impossible to get correct yes and no algorithmically.




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

Search: