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-14 4:14
I don't understand what you are trying to ask >>1-kun. The halting problem is whether a magical algorithm that can decide if any algorithm terminates or not for certain domain exist or not. And the answer is no, but of course you can create an algorithm that decides if some specific algorithm terminates or not. Read IATLC (Introduction to Automata Theory, Languages, and Computation).
Name:
Anonymous2016-09-14 5:56
Wouldn't it be easier to just decide if any program will always halt within some quickly-computable number n cycles?
Name:
Anonymous2016-09-14 6:14
Or a program that calculates big O would seem feasible
Name:
Anonymous2016-09-14 6:32
Assuming those two functions signatures are F(function, arguments), then both would not halt. Let C = caller, in this case G or P. we are executing C(C)...
Assuming at some point F calls function(arguments), C(C) would be called again, resulting in non-halting. But since F is not allowed to execute function(arguments), then no matter what way you imagine it to be implemented, when the program flow forms a cycle, it would either raise an error or not halt. Basically it seems like to make ReturnsOdd(f, args) or anything of the sort, you would have to solve the halting problem; determining program flow being a subset of the halting problem--if this was your point then I agree.
All programs eventually halt when i shut the computer down.
Name:
Anonymous2016-09-14 13:13
But is there a point in knowing a program will take a non-infinite number of eons?
Name:
Anonymous2016-09-14 13:37
>>9 each 40 years American BMI rises 3 points. How many years since 1960 remains until Earth becomes a neutron star?
Name:
Anonymous2016-09-14 14:09
[B][B][C][o][d][e]~PHALE~[/B][/B][/C][/o][/d][/e]
Name:
Anonymous2016-09-14 14:17
>>2 What about a magical algorithm that can decide if any algorithm returns an odd number? Why wouldn't P(P) prove the undecidability of this more specific problem?
Yes I understand the proof. But something still bothers me--a human can figure out whether or not a small program halts (or returns odd, etc.) by looking at the source and acceptable inputs. Why can't strong AI solve the halting problem then?
>>17 both humans and algorithms can solve some specific cases but there is no possible general solution unless you have a Zeno machine.
Name:
Anonymous2016-09-15 7:44
speaking of Zeno machine, did you know that from a mathematical perspective, countably infinite (aleph zero) sets include natural numbers, integers, primes and dubs (check'em)?
We might be able to solve the real-world useful version of the halting problem if it weren't for academic bullshiters who write retarded counterexamples.
>>27 The idea is that for any implementation of Halts(), you can devise a program (such as what you quoted) for which it won't work on. Therefore it cannot exist.
Name:
Anonymous2016-09-15 21:27
If we had Turing-complete hardware, we wouldn't need infinite (or any other kind of) compression.
Name:
Anonymous2016-09-15 21:34
>>30 That's like saying it's impossible to have strong materials because there will always be a nigger who tries to break it in half.
Holy shit, just restrict the problem to the space of programs that don't moronically contradict themselves and lie to the halting function, end of the goddamned fucking problem.
don't moronically contradict themselves and lie to the halting function
So you're supposed to already know whether or not the program halts before you pass it to the halting function?
Name:
Anonymous2016-09-15 23:44
>>33 No, just use the space of programs that don't call the Halts() function. Every single program in existence right now is in this space, including programs that don't halt and programs that do.
Name:
Anonymous2016-09-16 1:07
>>34 Then you'd be solving only a subset of the halting problem.
>>35 The only practically useful subset of the halting problem, which academics refuse to solve because of some stupid counterexample.
Name:
Anonymous2016-09-16 2:33
>>36 The computational power required to solve the halting problem for any non-trivial real program would still be immense. It would make brute-forcing a 32768-bit RSA key look easy.
Name:
Anonymous2016-09-16 6:53
>>37 Considering only a limited subset of sequences of assembler instructions make sense and don't crash, the number of valid programs is much smaller than you think.