1
$\begingroup$

I've been reading about building Turing machines for specific purposes, and some sources talk about input encodings and some talk about programming specific machines, but I've been unable to find anything that discusses both. Here's a specific set-up:

Suppose you have a universal Turing machine. It has a two-sided infinite tape, where the right side encodes a specific function to compute and the left side encodes the input to be provided to that function.

In general, I'm interested in the interaction between the encoding of the input, the specific program for the TM, and which UTM it is. My main question is:

If I have a fixed underlying UTM, a fixed encoding of the input, and a desired function to compute, can I always find a way to program my UTM to compute that function on the input supplied in the specified encoding?

For example, if I have the (2, 18) universal Turing machine, I encode the input using the system described here, and know that I want to compute the function $f(x, y, z) = x^3+xy+z^9$ is there guaranteed to be a program I can use to achieve this result?

I am under the impression that the answer is yes, but am not sure enough of my knowledge of Turing machine architecture to prove it.

More generally, if we think of this set up as having four parameters - the specific UTM, the specific input encoding, the specific function, and the specific program - is it always the case that if we fix three of these four parameters there will be a setting for the fourth?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ I don't really understand your question. You can program a Turing machine to do anything that is computable. So, as long as you can translate between input encodings in a computable way, the input encoding doesn't affect computability. OK, that sounds a bit circular but you can use "Is it possible to write a Java/Python/whatever program to do that?" as a proxy for "is it computable?" $\endgroup$
    – David Richerby
    Commented Nov 7, 2018 at 17:57
  • $\begingroup$ Indeed, along those lines, does it help your understanding if you replace the words "UTM", "TM" and "input encoding" with "Python interpreter", "Python program" and "data format"? $\endgroup$
    – David Richerby
    Commented Nov 7, 2018 at 17:59
  • $\begingroup$ @DavidRicherby That was my impression, but when challenged I was unable to fully justify an answer. For example, Python doesn’t have direct bit access to memory. There are programming languages that do allow direct bit access, but my understanding is that they come with architecture or programming restrictions. I know that I can write a program to compute my function, but I don’t know if I can always do that in such a way to satisfy arbitrary architecture requirements. $\endgroup$
    – Stella Biderman
    Commented Nov 7, 2018 at 18:11
  • $\begingroup$ Or, I think that I can (as I said in the question) but I don’t know how to prove it (I don’t particularly understand tag games, which seems relevant). $\endgroup$
    – Stella Biderman
    Commented Nov 7, 2018 at 18:12
  • $\begingroup$ "Direct memory access" doesn't matter. Just declare a big array and use that as your memory, manipulating it however you see fit. $\endgroup$
    – David Richerby
    Commented Nov 7, 2018 at 18:13

2 Answers 2

Reset to default
1
$\begingroup$

I'm going to simplify your question, considering that a specific encoding for a universal Turing machine will necessarily include a method for the encoding of its programs. I'll also assume that the encoding of programs and their inputs are also interdependent, meaning that you can't define how the former is done well enough without defining how the latter is done, equally well, and vice-versa.

What's left for us to do then, is to be able to explore the correspondence between programs and mathematical functions. We know that there are functions that are definable, but not computable (there isn't a corresponding program). We tend to assume that every program is the encoding of a function, but that's debatable.

So, you ask (as I understand): if there is a program that computes a function under a specific encoding of the input, for a specific encoding of the machine on which it runs, if one of these encodings change, will the function still be "writable"?

The answer would have to be that, if this is not the case, then that proves the encodings are not really equivalent, i.e., the computational models they define are substantially different. In other words, with a change in encoding should come a proof of equivalence, and what that proof states is exactly that the different encodings should be able to write the same functions $-$ if writable they are.

Improve this answer
$\endgroup$
0
$\begingroup$

Perhaps you are searching for the definition of computable functions. If your function is computable, there is a turing machine.

In more detail: If your desired function is expressible as a computable function on any encoding and if there is a computable translation between that single encoding and your desired encoding, then the function is computable on your desired encoding too.

For example let your desired function and encoding be f : E -> V (encoded input to result values). If there exists a positive integer k and computable functions t1 : |N^k -> E (surjective, with computable right-inverse) and t2 : V -> |N (injective, with computable left-inverse) such that the composition g = t2 . f . t1 : |N -> |N is computable (this might be proven by giving an algorithm for it), then f is computable too.

Improve this answer
$\endgroup$

Your Answer

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

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