0
$\begingroup$

Turing test of Artificial intelligence relies on interaction between two parties with the goal that one party convinces the other party that it has the same computational abilities.

I'm trying to formalize a new notion of machine Intelligence: the ability of Turing machines (algorithms) to recognize their programmer and that they were not generated randomly. This requires defining metrics to be used by Turing machines to measure the creative abilities of the programmer. We may allow interaction between the algorithm and the programmer.

How can we formalize such notion of AI? Has any similar idea been investigated before in TCS?

EDIT1: programmer here is a program that is able to generate other algorithms runnable on some computing device.

One motivation is whether intelligence of an algorithm is dependent on programmer's intelligence.

EDIT2: I'd like to formalize a notion for the intelligence and creativity of programs. Not all programs created equal. My question is an attempt to model and formalize aspects of intelligence that are not captured by current definitions of AI. For instance, Does an evolutionary algorithm possess any intelligence? If yes, What is the source of this intelligence?

EDIT3: My goal is to remove the subjectivity from Turing test. If the programmer is able to convince a Turing machine that it was the product of creativity of the programmer then the Turing machine is intelligent. Furthermore, the programmer is far more intelligent than the code he created. So, the challenge is how to formally convince the Turing machine that the programmer has superior computational abilities. In addition, the programmer must convince the Turing machine that those superior computational abilities are required and critical to the creation of the Turing machine code.

Improve this question
$\endgroup$
15
  • 7
    $\begingroup$ I don’t understand the question. What’s a “programmer”? $\endgroup$
    – Jeffε
    Aug 14, 2011 at 14:01
  • 2
    $\begingroup$ What if the "program" had evolved and would neither have appeared randomly nor have had an explicit creator? $\endgroup$
    – Lev Reyzin ♦
    Aug 14, 2011 at 16:59
  • 1
    $\begingroup$ Along the lines of Lev's comment, TCS has actually been used to study evolvability, an example is Valiant's paper. $\endgroup$
    – Artem Kaznatcheev ♦
    Aug 14, 2011 at 17:14
  • 1
    $\begingroup$ +1 for a creative question that seems constructive: If the program can modify itself, how will it know itself from the programmer? $\endgroup$
    – Niklas Rosencrantz
    Aug 14, 2011 at 18:42
  • 2
    $\begingroup$ I did not downvote this question because it's potentially interesting, but I think it needs rewording so we know what you're really asking. $\endgroup$
    – Lev Reyzin ♦
    Aug 14, 2011 at 18:52

3 Answers 3

Reset to default
8
$\begingroup$

Let me give a partial answer from a learning theory perspective. As your question isn't well specified, this answer won't be either. In my answer, I'm assuming your question was inspired by your blog post, linked from your profile.

Say that you are thinking about programs that are just functions (so they have to halt, etc.). You can ask whether certain classes of such functions can appear randomly by, perhaps, looking at the probability a random program (from some distribution that you think is likely) lands in that class or not, with the hope that probability is polynomially large. I haven't really thought this argument through.

You can also ask whether such a class is efficiently evolvable according to Valiant's model of evolution (also in @Artem's pointer in comments): luckily what is efficiently evolvable is known to be the class learnable by correlational statistical queries; taking "crossover" into account, you get parallel correlational statistical queries. One thing to note is that just because evolvability is characterized, it is still a separate and sometimes difficult task to determine whether a particular class is evolvable (learnable with CSQs) or not.

If you find a class of "programs" that is neither randomly occurring nor evolvable, perhaps you can conclue it has a "creator/programmer," though that conclusion may still take a leap of faith.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks Lev. Aren't the rules that govern the evolution of programs expressable by some program (not necessarly halting)? $\endgroup$
    – Mohammad Al-Turkistany
    Aug 14, 2011 at 21:31
  • $\begingroup$ Sure. But I don't know what you're getting at... $\endgroup$
    – Lev Reyzin ♦
    Aug 14, 2011 at 23:55
  • 5
    $\begingroup$ Why not keep going and ask whether randomness could be randomly created? It's turtles all the way down. (On a more TCS note, if you want to address your suggestion via cs theory, you have to carefully define your model. What does it mean to be randomly generated; with what probability? Which programs are allowed and which ones aren't? What outputs are allowed? Are the functions boolean? What is the class of evolution functions? What are you trying to learn? These things need to be nailed down...) $\endgroup$
    – Lev Reyzin ♦
    Aug 15, 2011 at 2:39
  • 1
    $\begingroup$ We can not have a circular definition for Randomness. My question is not about Randomness. It is about intelligence and creativity of programs. Not all programs created equal. My question is an attempt to model and formalize aspects of intelligence that is not captured by current definitions of AI. What is the source of intelligence in an evolutionary algorithm? $\endgroup$
    – Mohammad Al-Turkistany
    Aug 15, 2011 at 9:00
  • 1
    $\begingroup$ Define IQ for non-humans? I once posted a question whether a software that is written to solve an IQ-test can be considered "intelligent". It was closed as not a real question and they didn't think that I should be admitted to ask something like "What's the intelligence of a software?" therefore I think this post elaborates on the topic I too wanted. I don't know of a robot or software that has been trained or programmed to solve an IQ test better than randomness but it shouldn't be impossible since you can built the robot with a camera that reads and answers to questions on an IQ test. $\endgroup$
    – Niklas Rosencrantz
    Aug 16, 2011 at 21:56
5
$\begingroup$

If I understand your question correctly, it attempts to relate intelligence to reproduction. The connection between the two goes back to the very beginning of the theory of applied computation. von Neumann in 1948 envisioned a robot that could duplicate itself completely. First it assembled all the pieces of the robot. Then it copied the memory tape that it had itself. Then it placed the memory tape in the new robot. However, von Neumann never published this, and it was not until 1966 that Burks fleshed out his notes into a proof, in Theory of Self-Reproducing Automata, that it became public.

This paper was one of the precursors of the field of Artificial Life. Broad brush, there are two philosophical positions in that field: "strong alife," and "weak alife." Weak alife states that any living process must be chemical in nature. Strong alife states that a living process can occur in any medium. (So, for example, software entities could be alive, whatever "alive" means.) von Neumann was an early believer in strong alife, it appears.

There are a great many algorithms that try to produce descendents that are fitter (i.e., more able to solve problems that require some form of "intelligence" to solve), and different algorithms have different metrics of success. Luc Steels wrote a book on this general subject in 1993: The Artificial Life Roots of Artificial Intelligence.

I don't know how to steer you more specifically, but perhaps you will find a vocabulary in those works that will help you ask a more precise question. Good luck.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ As a side note, previous to von Neumann/Burks, I think most biologists were fine with a definition of LIFE as "a system that reproduces." Now, more is needed for something to be alive, much less intelligent. $\endgroup$
    – Aaron Sterling
    Aug 15, 2011 at 19:44
-1
$\begingroup$

I think quantifying computer intelligence by something so unquantifiable as the creativity of its author might prove unfruitful. It is an interesting notion, however. I would perhaps look at how large or complex the language is that the TM accepts. This is much easier to quantify, and it has been shown that there is a 1-1 correspondence to a TM and its language. It follows that if the TM's language is more complex, the machine is more "intelligent".

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ Incorrect. Given a TM it's easy to construct a new TM that accepts the same language by adding a/some dummy state(s). Also, it's highly questionable that the size of a language corresponds to its complexity. $\endgroup$
    – Huck Bennett
    Aug 15, 2011 at 20:35

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.