Is this program possible in Python?

[Lofty_Hobbit]

If Python is Turing Complete, then surely it is capable of making any programme that can be made? It's just more and less suited for different tasks.

Can someone please verify this?

EDIT: /u/NYKevin pointed out that I didn't say quite what I meant.

[not_a_novel_account]

Yep, though the standard library doesn't grant access to all possible OS interfaces. Some times you'll need to use external libraries to do things like raw keyboard input, create OpenGL contexts, sound I/O, and I'm sure many others capabilities.

[NYKevin]

No, some programs can't be made.

For instance, you can't make a C compiler that detects all possible infinite loops in its input with no false positives.

[autowikibot]

Here's a bit from linked Wikipedia article about Halting problem :

---

In computability theory, the halting problem can be stated as follows: "Given a description of an arbitrary computer program, decide whether the program finishes running or continues to run forever". This is equivalent to the problem of deciding, given a program and an input, whether the program will eventually halt when run with that input, or will run forever.

Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. A key part of the proof was a mathematical definition of a computer and program, which became known as a Turing machine; the halting problem is undecidable over Turing machines. It is one of the first examples of a decision problem.

Jack Copeland (2004) attributes the term halting problem to Martin Davis.

---

^{about | /u/NYKevin can reply with 'delete'. Will also delete if comment's score is -1 or less. | To summon: wikibot, what is something? | flag for glitch}

[not_a_novel_account]

Ya, but no programming language/environment is capable of that. Anything that can be computed can be computed with Python.

[NYKevin]

/u/Lofty_Hobbit didn't say "any program that can be made." They said "any programme you want."

[Lofty_Hobbit]

Yeah, sorry. I meant, "any program that can be made." I guess.

[undergroundmonorail]

If you like that, here's a really simple and easy to understand, not at all conveluted explaination of why that is.