>>45
Alright, I'll do it better this time.
Part one, showing that determining whether or not a statement is executed is undecidable. Suppose for the sake that determining whether or not a statement is executed is decidable. We will reach a contradiction by showing that the halting problem is decidable. Here is the solution:
function halts(A)
function B()
A()
execute_special_statement()
end
statement_would_be_executed = inspect_B_and determine_if_execute_special_statement is executed
return statement_would_be_executed
end
If A halts, then execute_special_statement will be executed, and halts(A) will return true. If A does not halt, then execute_special_statement would never be executed, and halts(A) will return false. Because the process of determining whether execute_special_statement will halt or not is assumed to be a decider, then we have that halts is also a decider. By producing a solution to the halting problem that halts on all its inputs we have shown that the halting problem is decidable, which is a contradiction. Hence, the problem of determining whether a statement is executed or not must be undecidable.
Part 2: Showing that perfect type prediction is undecidable. Suppose for the sake of contradiction perfect type prediction is decidable. We will reach a contradiction by showing that determining whether or not a statement is executed is decidable. Let A be an arbitrary algorithm, with a() being an arbitrary statement within A.
function A()
...
a()
...
end
We will produce an algorithm, Executes(A,a) that will return true if a() is executed when A is ran, and false if a() is not executed when A is ran, and we will show that Executes halts on all inputs.
We will produce a new algorithm from A, called B, defined as follows:
function B()
my_var = "lol I'm a string"
<first chunk of code from A>
{
my_var = 1337
a()
}
<second chunk of code from A>
print(my_var)
end
note that my_var is a string when it is printed if and only if a() is never executed, and my_var is an int if and only if a() is executed.
function Executes(A,a)
let B be defined in terms of A and a, as above
my_var_type_when_printed = predict_type_when_printed(B, 'my_var)
if my_var_type_when_printed == 'int' then
return true
else
return false
end
end
Executes is a decider, because it relies only on type prediction, which is assumed to be decidable. Executes correctly determines when a is executed within A, because my_var becomes an int if and only if a() is executed within A. So Executes is a solution to the problem to checking whether a statement is executed or not, that halts on all inputs, which shows that the problem of determining whether a statement is executed or not, is decidable, which is a contradiction. Therefore, the initial assumption of type prediction being decidable must be false.
>>47
yeap, just like every other irc channel, right?