3 ms·
Standard proof is a diagonalization, which depends on infinite sequences. That said, the Halting problem on physical computers is still of extremely high compu
by naasking 7y ago
Standard proof is a diagonalization, which depends on infinite sequences.
That said, the Halting problem on physical computers is still of extremely high computational complexity, which can be just as high a barrier as incomputability.