constant escape

winter withered, warm
What if consciousness has something to do with a contrivedly sustainable non-halting? I could be missing something, in terms of understanding precisely what the halting problem is. Seems to refer to a turing machine, which I can't quite distinguish from an algorithm, only being valid if it halts. Halting seems to be a necessary but insufficient condition.

edit: only deferring to computational lingo here, not actually asserting that turing machines and the human brain are engineered in a recognizably similar way.
 

constant escape

winter withered, warm
But how is it "in advance" if you need to run the thing to see if it halts? Can you know whether or not it halts before running it?
 

vimothy

yurp
halting problem means that theres some level of code analysis which its not possible for a machine to perform
 

poetix

we murder to dissect
no thats the meaning of the halting problem. you can't tell in advance if it will terminate.
a) You often can: I know that

10 PRINT "I WILL NEVER LOG OFF"
20 GOTO 10

doesn't terminate, and I know that

10 LET A = 10000000000000000
20 LET A = A - 1
30 IF A > 0 GOTO 20

does, eventually.

b) Running it only tells you that it terminates if it terminates while you're running it; if it doesn't, well maybe it would have if you'd left it running for longer. In fact, for any finite number n it's theoretically possible to write a program that can determine with certainty whether another program/input combination will terminate within n steps. That program might not give the right answer for n+1 steps, though, and the program that would give the right answer for n+1 steps might not give the right answer for n+2 steps, etc.

(edit: just realised that's a bit of a red herring: you can write a program that takes n as a parameter that, for all finite n, can determine with certainty whether another program/input combination will terminate within n steps, so it's not like it would have to be a different program for different values of n. What does this magic program do? Worst case scenario, it emulates the execution of the other program for n steps, or until termination, then tells you which has happened. Which is morally the same as "running" it, but the halting problem is not, actually, the problem that you "have to run a program to know whether it will terminate", but the problem that even a program that can run another program for a finite number of steps cannot use this method to determine, for all program/input combinations, whether they will ever terminate)

What isn't possible is to write a program that can determine, for all program/input combinations, whether there exists a number n which is the number of steps the other program will run for before terminating.
 
Last edited:

vimothy

yurp
my understanding is that it is impossible to write a programme which can tell whether, for an _arbitrary_ input programme, that programme will terminate
 

poetix

we murder to dissect
my understanding is that it is impossible to write a programme which can tell whether, for an _arbitrary_ input programme, that programme will terminate
I believe it's "for an arbitrary program and input, whether the program will terminate given that input", and the problem is that program/input pairs themselves may be given as inputs, which enables you to set up a paradox of self-reference:

1) Given I have a program H(P, x), which returns 1 if the program P halts for the input x, and 0 otherwise,
2) I construct an evil program E(P), which uses H to determine whether P halts for the input P, and then either returns 1 if H(P, P) = 0 (P does not halt for P, according to H), or loops infinitely if H(P, P) = 1 (P does halt for P, according to H).
3) Now I ask H(E, E) to tell me whether E will halt for the input E. If H(E, E) = 1, then the actual behaviour of E(E) will be to loop infinitely; if H(E, E) = 0, then E(E) will return 1 and halt - the opposite of the result H should give. Contradiction!

Turing used this to demonstrate that the halting set is non-computable, as part of a general proof that there must be non-computable real numbers. You can think of the halting set as a real number, provided that programs plus inputs are enumerable, i.e. for every counting number n there is an "nth" program/input combination. The halting set could then be represented as an infinite digital expansion 0.10110100... with a 0 or 1 for every nth digit depending on whether the "nth" program/input combination halts. This number is non-computable, per the halting problem, therefore there is provably at least one non-computable real number.

Another way to think about this is in terms of the relationship between countable and uncountable sets. Because every program/input combination can be represented as an integer, the set of all possible program/input combinations is countably infinite, i.e. it's the same size as the set of counting numbers 0, 1, 2 etc. Some irrational real numbers, such as pi, are computable, in the sense that you can write a program PI( n ) that will eventually halt and give you the nth digit of pi for any n. But because there is (per Cantor) no possible bijection between the set of counting numbers and the set of real numbers, which is uncountably infinite, there must be non-computable real numbers. (In fact, to a first approximation, all real numbers are non-computable, in that a randomly-chosen real number is non-computable with probability 1).
 
Last edited:

poetix

we murder to dissect
Maybe the countable/uncountable infinity distinction was the real ontic/ontological distinction all along
 
Top