2
$\begingroup$

I understand the notion of the universal Turing machine ($U$), which receives a pair of Turing machine ($M$) and an input to $M$ ($x$). If $M$, which obtains $x$, outputs $y$, $U$, which obtains $(M, x)$, outputs $y$ as follows:

$M: x \mapsto y \\ U: (M, x) \mapsto y$

My question is whether there is a theory of another type of Turing machine where the output (not input) of Turing machine is another Turing machine like:

$U': x' \mapsto M$

I guess a program which generates another program can be regarded as this kind of Turing machine $U'$. If so, automatic code generator and machine learning algorithm might be regarded as this type of Turing machine.

(Maybe, brains of human programmers can be modeled using a theory of such Turing machines because a source code seems a form of Turing machine.)

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Like, every functional programming language? I'm confused by this question. You seem to accept that Turing machines can be represented as numbers (you should really write $\langle M \rangle$ as input), numbers can be the ouput of a TM, so: yea, of course that's possible! In the standard theory. $\endgroup$
    – Raphael ♦
    Aug 29, 2017 at 4:47
  • $\begingroup$ @Raphael Of course, I understand Turing machine can output another Turing machine. My concern is whether there is a (interesting) theory about such Turing machine. Turing machines receiving (<M>, x) can be the Universal Turing machine, which has very interesting properties. I'd like to know whether there is interesting theory about Turing machine providing another Turing machine. I guess machine learning or automatic coding are candidates. $\endgroup$
    – Light Yagmi
    Aug 29, 2017 at 11:09
  • $\begingroup$ I'm afraid that's way too broad then: there are many, many instances of such behaviour. Community votes, please! $\endgroup$
    – Raphael ♦
    Aug 29, 2017 at 13:53
  • 1
    $\begingroup$ @rkjt50r983 Yes, recursion theory, or computation theory studies this in details. See, for an example, the $s_{mn}$ theorem for a starter. $\endgroup$
    – Pål GD
    Aug 29, 2017 at 14:33
  • $\begingroup$ Have you tried to make any such interesting machines outputing machines by yourself? $\endgroup$
    – Andrej Bauer
    Aug 29, 2017 at 20:39

1 Answer 1

Reset to default
2
$\begingroup$

It depends on what your are referring as "theory" (which basically means everything or anything).

Something which is closely related to what you are referring can be the field of Program transformations, which tries to study systematically programs that modifies other programs. The original interest of this field is the transformers that are semantically invariants (with a bit of hand waving: you want to study transformers $T$ such that for any program (or a TM) $p$, $T(p)$ does the same thing as $p$). Derives from these original considerations the subfield of program synthesis (here, given some input datas, you want to automatically generate a program that satisfies some conditions encoded by you input).

A good introduction can be the thesis of M. Ward "Proving Program Refinements and Transformations" with an emphasis on the proof of program side.

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.