Wikipedia:Reference desk/Archives/Mathematics/2023 January 3

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

January 3

Why halting problem is unsolvable? We can write a program to avoid self-reference like Microsoft Excel

The proof that halting problem is unsolvable uses the self-reference, i.e. def g(): if halts(g): loop_forever(), however, in many programs such as Microsoft Excel, in Microsoft Excel, if we type “=A1+1” in the lattice A1, then it will returns “Error: Self reference!”, thus we may write a program that can detection self-reference, and if we write “def g(): if halts(g): loop_forever()”, then it will return “Error: Self reference!” 118.170.3.8 (talk) 06:49, 3 January 2023 (UTC)

Direct self-reference is not essential for the proof. Turing's original proof did not involve direct self-reference. It is only in later, popular presentations that direct self-reference appears. These presentations sketch the proof with a program that uses direct self-reference as a shortcut. If you can write a self-reproducing program in some language without "cheating", you can use the same method to create a proof that solely relies on indirect self-reference. This should be possible in any reasonably expressive language, by the diagonal lemma. Detecting such indirect self-reference is itself an unsolvable problem.  --Lambiam 10:31, 3 January 2023 (UTC)

I'm pretty sure the self-reference issue in Excel is a different animal than self-reference in mathematical logic. The problem of determining if an Excel spread sheet contains self-reference reduces to that of determining if a finite directed graph is acyclic, which is clearly solvable. You might be able to use a spreadsheet to implement more complex algorithms, but a formula in a spreadsheet cell can only refer to other cells, not the spreadsheet itself considered as an algorithm. In any case, the job of a popular presentation is to make you think you understand something you really don't, so it's not a good idea to reason using one as a starting point. --RDBury (talk) 15:38, 4 January 2023 (UTC)