-2
$\begingroup$

My understanding is that Python is "Turing complete" which mean they work on the same axioms (or by first order logic equivalent) as a theoretical Turing machines (https://en.wikipedia.org/wiki/Turing_machine).

So what are the axioms which govern how Python programming language works? Are they same as Turing machine's axioms?

I argue that if you want to be able to say that Python is Turing complete then it implies that Python has axioms. Because the way to say that two systems can do the same (Python and Turing machine) means that there is a rigorous mathematical proof which shows that the rules of Python are equivalent to Turing machines.

I would like to see the listed axioms of Python listed in the answer. Like the wikipedia page of Turing machine list the axioms of Turing machine.

I see this as an important aspect because those axioms restrict the actions the languages or machines can do. Thank you!

$\endgroup$
2
  • $\begingroup$ Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. $\endgroup$ Commented Jun 9 at 18:33
  • $\begingroup$ Ask one question per post please. $\endgroup$ Commented Jun 9 at 18:42

1 Answer 1

Reset to default
6
$\begingroup$

Computer languages don't have axioms. They have specifications, written in ordinary English that includes some technical and mathematical terms.

There are convincing arguments that Python and R and other high level languages can calculate anything a Turing machine can calculate. Those arguments don't really depend on how Turing machines are defined in ZFC.

$\endgroup$
3
  • $\begingroup$ I think "convincing argument" here can be replaced by "proof", provided Python and R are sufficiently precisely defined. What's needed for the proof is essentially just a Python or R program for simulating a Turing machine, and that should be easy to write. (I'll settle for convincing arguments for the converse, although a proof would be possible in principle --- "just" simulate Python or R on a Turing machine). $\endgroup$ Commented Jun 9 at 21:17
  • $\begingroup$ @AndreasBlass I'm OK with that, but won't make the edit. There's a possible problem if you require a proof that the simulation program is correct. $\endgroup$ Commented Jun 9 at 21:41
  • $\begingroup$ @EthanBolker I think if there is a proof then it implies that there are axioms for programming languages. If you prove that something is Turing complete by comparing the outcomes of two systems then you need to compare the rules (or axioms) of the both systems. Or whatever derives the outcomes of the system. $\endgroup$ Commented Jun 9 at 22:36

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.