Halting problem = undecidability of all program properties?
Name:
Anonymous2016-09-14 3:28
[i]UNDERGRAD QUALITY[/i] incoming: An old thread on /math/ got me thinking about this. We know the typical proof uses func G(x): if Halts(x, x) then loop forever else false and G(G) as a counterexample. Would this func P(x): if ReturnsOdd(x, x) then 2 else 1 mean you can't prove a program always returns odd numbers because of P(P)? What about any other simple property like ``returns alphanumeric character'' or ``returns a valid s-expression''? You can always construct a function that ends in a contradiction by just returning the opposite thing.
Name:
Anonymous2016-09-16 9:55
>>40 create random textfile and read it out loud. with a very high probability, it won't be correct English or comprehensible English or even a collection of pronounceable words. but it doesn't mean that a set of all unique possible texts in correct (or just comprehensible) English is small. in fact, without size restrictions such a set is infinite.
>>42 ok then, let's test all valid programs within a certain size restriction. HDD size could be a good, realistic constraint: we won't test programs bigger than 1TB.
of course this is all pointless because even if we're able to test those programs, some of them will keep running without there being a way of determining whether they will eventually halt or not. read up about busy beaver candidates - some of them have been running for years and we still don't know if they're halting or not.
Not sure whether OP is trying to be witty here, but isn't this exactly what Rice's theorem is about?
How come this thread has 56 replies and not a single person has pointed out OP is a retarded undergrad who just failed his first Automata Theory 101 exam?