2
$\begingroup$

Assume I have a programming language $L$ with well-defined semantics. Showing Turing-completeness is straightforward: if I write a program using $L$ simulating the universal TM, I'm done. What I'm concerned about is another direction. How do we show that a program in $L$ can be simulated by TM when $L$ supports things like:

  • File I/O (I guess this can be handled by considering the entire filesystem as the part of the tape?).
  • Interactive user input (I guess we can treat it as non-interactive?).
  • Interaction with external devices, e.g. display, network, etc. (I guess it can be handled by the file interface?).
  • Assume that the semantics is non-deterministic (e.g. $L$ allows parallel execution). How to fit it into TM settings?
  • Probably many other things I didn't think of...

I'm fine with a reference that covers this question. Note that I'm talking about the language itself, not about its implementations, and hence the Church-Turing thesis is not applicable: e.g. a Turing complete language which also has access to the Halting oracle is not Turing equivalent.

Improve this question
$\endgroup$
7
  • $\begingroup$ "e.g. the language can allow the operation 'solve the halting problem'". This example is so controversial that it makes your point much more confusing. Could you come up with another example? Or please explain exactly your meaning of "solve the halting problem". $\endgroup$
    – John L.
    Jun 29, 2022 at 18:18
  • $\begingroup$ @JohnL., The language might define function $HALT(TM, x)$, which returns $true$ if Turing machine $TM$ halts on input $x$ and $false$ if it doesn't. Just imagine that e.g. I defined my language Python++ by taking Python and adding this function to its specification. Of course, no complete implementation of such language exists (which is also true for many popular languages), but the language and its semantics are mathematically defined. The controversy of the example is exactly the point, so that one can't just say "the other direction is by the Church-Turing thesis". $\endgroup$
    – Dmitry
    Jun 29, 2022 at 18:34
  • 1
    $\begingroup$ To show that "a program in $L$ can be simulated by a TM", we can assign "semantics" to each symbol in the tape alphabet and each state so that we can interpret the TM as operating on /interacts with files, users, display, etc. In general, we will be able to verify that whatever the program can do, provided that $L$ is "reasonable" or "practical", there is a TM that can do that too. Well, that is, basically, Church-Turing thesis. $\endgroup$
    – John L.
    Jun 29, 2022 at 18:37
  • $\begingroup$ @Dmistry "The language might define function $HALT(TM,x)$, ...". Then I would object "the language and its semantics are mathematically defined". I would say, sorry if I am being blunt, that language is meaningless. On the other hand, if you insists it is well-defined, then you are defining a language with "oracles", which should be simulated by Turing machines with oracles $\endgroup$
    – John L.
    Jun 29, 2022 at 18:41
  • 1
    $\begingroup$ But, if you postulate that your language is able to compute the halt function, doesn't that automatically mean that it's not Turing-equivalent (because you know it can compute something that a Turing machine cannot; you know from the get-go that they are not equivalent - you don't need to invoke the Church–Turing thesis at all). $\endgroup$
    – Filip Milovanović
    Jun 29, 2022 at 19:17

1 Answer 1

Reset to default
3
$\begingroup$

First of all you should separate the (math) specifications of $L$ and its "execution" from the input/output functions of $L$. If such input/output is crucial for $L$ then you're trying to prove the Turing equivalence of a "device running $L$" with a Turing machine (which is a little bit different).

For example if $L$ has a function "read random bit from device X", then it's probably easy to prove the equivalence of $L$ with a Turing machine; but the combo "$L$ + an actual Geiger counter" leads towards the "physical Church–Turing thesis".

You must first model all aspects of $L$ (I/O, user input, ...) in terms of reading/writing into tapes. And this can usually be done in a very simple way:

  • file/io --> tape
  • output devices --> tape
  • interactive user input --> special tape in which user input is pre-loaded
  • parallelism --> already a lot of work on it and its TM modelization
  • non determinism --> NTMs
  • ...
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.