Hacker News Reader

Surprised nobody has mentioned the halting problem [1] yet, which logically proves programming can never be automated.

[1] https://i.imgur.com/HVeO7ek.png (CH 8, Algorithms - Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh V. Vazirani)

View on HN

The halting problem doesn't prove that at all. It just shows that there exist programs who's output can't be predicted except by running them (potentially forever). It obviously doesn't prove that all programs have that property. I mean, we write programs which provide useful output then halt every day.

And if humans can write code, a sufficiently advanced AI will be able to write code too.

You can use Rice's theorem[1], which is a generalized version of the Halting problem.

I don't believe this proves that programming can't be automated, though. Humans too aren't able to prove completely that what they write is correct, it doesn't stop them from making programs.

[1] https://en.wikipedia.org/wiki/Rice%27s_theorem

Reply on news.ycombinator.com