<p>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 <a href="http://turkistany.blogspot.com/2011/01/theory-of-computing-and-intelligent.html" rel="nofollow">blog post</a>, linked from your profile.</p>

<p>Say that you are thinking about programs that are just functions (so they have to halt, etc.).  You can ask whether certain <strong>classes</strong> 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.</p>

<p>You can also ask whether such a class is <a href="http://people.seas.harvard.edu/~valiant/evolvability-2008.pdf" rel="nofollow">efficiently evolvable</a> 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 <a href="http://www.eecs.harvard.edu/~vitaly/papers/F_strongSQD_manu0614.pdf" rel="nofollow">correlational statistical queries</a>; taking "crossover" into account, you get <a href="http://people.seas.harvard.edu/~varunk/docs/evolution-K11.pdf" rel="nofollow">parallel correlational statistical queries</a>. 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.</p>

<p>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.</p>

CC BY-SA 3.0
2011-08-14T21:31:07.737Z
Thanks Lev. Aren't the rules that govern the evolution of programs expressable by some program (not necessarly halting)?
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-08-14T23:55:47.457Z
Sure. But I don't know what you're getting at...
Lev Reyzin
CC BY-SA 3.0
2011-08-15T02:09:54.903Z
You can not reduce intelligence in the evolutionary algorithm to evolution itself or randomness. The evolution mechanisms contain intelligence which can not be produced by evolution. I suggest that intelligence is conserved. A program can not be more intelligent than its creator.
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-08-15T02:39:02.940Z
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...)
Lev Reyzin
CC BY-SA 3.0
2011-08-15T09:00:16.163Z
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?
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-08-16T21:56:01.003Z
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.
Niklas Rosencrantz
CC BY-SA 3.0
2011-08-14T18:26:05.163Z
2011-08-14T23:56:27.033Z
2011-08-14T23:56:27.033Z
Lev Reyzin
<p>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 <a href="http://cba.mit.edu/events/03.11.ASE/docs/VonNeumann.pdf">Theory of Self-Reproducing Automata</a>, that it became public.</p>

<p>This paper was one of the precursors of the field of <a href="http://en.wikipedia.org/wiki/Artificial_life">Artificial Life</a>.  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.</p>

<p>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: <a href="http://www.mitpressjournals.org/doi/abs/10.1162/artl.1993.1.1_2.75?journalCode=artl">The Artificial Life Roots of Artificial Intelligence</a>.</p>

<p>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.</p>

CC BY-SA 3.0
2011-08-15T19:44:21.303Z
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.
Aaron Sterling
CC BY-SA 3.0
2011-08-15T19:38:43.627Z
2011-08-15T19:38:43.627Z
Aaron Sterling
<p>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".</p>

CC BY-SA 3.0
2011-08-15T20:35:03.460Z
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.
Huck Bennett
CC BY-SA 3.0
2011-08-15T20:00:28.937Z
2011-08-15T20:00:28.937Z
djhaskin987
<p>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.</p>

<p>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. </p>

<blockquote>
  <p>How can we formalize such notion of AI? Has any similar idea been investigated before in TCS?</p>
</blockquote>

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

<p>One motivation is whether intelligence of an algorithm is dependent on programmer's intelligence.</p>

<p>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?</p>

<p>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.</p>

CC BY-SA 3.0
2011-08-14T14:01:48.230Z
I don’t understand the question.  What’s a “programmer”?
Jeffε
CC BY-SA 3.0
2011-08-14T16:59:28.143Z
What if the "program" had evolved and would neither have appeared randomly nor have had an explicit creator?
Lev Reyzin
CC BY-SA 3.0
2011-08-14T17:14:11.287Z
Along the lines of Lev's comment, TCS has actually been used to study evolvability, an example is [Valiant's paper](http://people.seas.harvard.edu/~valiant/evolvability-2008.pdf).
Artem Kaznatcheev
CC BY-SA 3.0
2011-08-14T18:42:55.223Z
+1 for a creative question that seems constructive: If the program can modify itself, how will it know itself from the programmer?
Niklas Rosencrantz
CC BY-SA 3.0
2011-08-14T18:52:56.333Z
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.
Lev Reyzin
CC BY-SA 3.0
2011-08-15T13:26:49.803Z
is a machine that starts counting at 1 and counts up indefinitely intelligent? Yet it generates all other TMs in the process... I don't understand the question.
Artem Kaznatcheev
CC BY-SA 3.0
2011-08-15T17:23:04.290Z
@Artem, Intuitively, a machine that exhaustively enumerates all solutions should not be considered intelligent. Therefore, Levin's Universal Search algorithm is not intelligent.
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-08-15T19:42:12.110Z
Maybe it is because I was a philosophy major, but I upvoted this.
Aaron Sterling
CC BY-SA 3.0
2011-08-15T20:22:39.057Z
IMHO this post is not answerable in its current form. It might be a nice idea but it is not developed enough to become a real question that can be answered. It will solicit opinion and discussion which I don't think is the purpose of cstheory. It is also probably more suitable for metaoptimize.
Kaveh
CC BY-SA 3.0
2011-08-15T21:57:20.303Z
I think this type of modelling question is more appropriate here than metaoptimize.  On the other hand, I agree that this question is vague enough to be hard to answer, and the clarifications have confused me more than helped.  IMO, this seems a rare example of a question that is (arguably deservedly) heavily downvoted, but doesn't meet the criteria to be closed.
Lev Reyzin
CC BY-SA 3.0
2011-08-15T22:14:05.720Z
I upvoted it because of the philosophical undertones too
Akash Kumar
CC BY-SA 3.0
2011-08-16T05:12:35.267Z
Just to remind people that cstheory is not a philosophy site, I don't think a question like "How can we formalize [some philosophical concept]?" is suitable question for cstheory, on the other hand asking for references for similar work would be OK IMHO. :) @Lev, as a user I am leaning towards closing as not-a-real-question ("It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form.") until Mohammad clarifies and improves it to a state that the question can be answered.
Kaveh
CC BY-SA 3.0
2011-08-16T05:17:44.900Z
Also see this ongoing [meta discussion](http://meta.cstheory.stackexchange.com/questions/1251/how-to-deal-with-how-to-do-x-questions-where-x-is-a-very-high-level-software).
Kaveh
CC BY-SA 3.0
2011-08-16T10:10:17.153Z
@Kaveh, The post clearly asks for references to works that address the weaknesses of Turing test. I'm asking for a better way to formalize the concept of machine (program) intelligence.
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-08-16T21:49:32.090Z
I voted +1 for this question and I like reading the comments and answers. I've taken a course in AI and it was just prolog programming with set theory, I read the AI book by Peter Norvig and Stuart Russel and that book just sums up basic concepts from other fields like probability theory, set theory and rule-based reasoning. I'm interested in self-modifying programs and the AI college course didn't even mention that and the Turing test was also not very formalized and like you say, it's subjective. Maybe you can look at patterns for cellular automata, machine learning and/or software bots.
Niklas Rosencrantz
<ai.artificial-intel>
Formalizing a notion of machine Intelligence
Mohammad Al-Turkistany
# Formalizing a notion of machine Intelligence

(Asked by: username_0 on 2011-08-14)

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.

**Tags:** ai.artificial-intel

> **Comments:**
> **username_1**: I don’t understand the question.  What’s a “programmer”?  
> **username_2**: What if the "program" had evolved and would neither have appeared randomly nor have had an explicit creator?  
> **username_3**: Along the lines of Lev's comment, TCS has actually been used to study evolvability, an example is [Valiant's paper](http://people.seas.harvard.edu/~valiant/evolvability-2008.pdf).  
> **username_4**: +1 for a creative question that seems constructive: If the program can modify itself, how will it know itself from the programmer?  
> **username_2**: 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.  
> **username_3**: is a machine that starts counting at 1 and counts up indefinitely intelligent? Yet it generates all other TMs in the process... I don't understand the question.  
> **username_0**: @Artem, Intuitively, a machine that exhaustively enumerates all solutions should not be considered intelligent. Therefore, Levin's Universal Search algorithm is not intelligent.  
> **username_5**: Maybe it is because I was a philosophy major, but I upvoted this.  
> **username_6**: IMHO this post is not answerable in its current form. It might be a nice idea but it is not developed enough to become a real question that can be answered. It will solicit opinion and discussion which I don't think is the purpose of cstheory. It is also probably more suitable for metaoptimize.  
> **username_2**: I think this type of modelling question is more appropriate here than metaoptimize.  On the other hand, I agree that this question is vague enough to be hard to answer, and the clarifications have confused me more than helped.  IMO, this seems a rare example of a question that is (arguably deservedly) heavily downvoted, but doesn't meet the criteria to be closed.  
> **username_7**: I upvoted it because of the philosophical undertones too  
> **username_6**: Just to remind people that cstheory is not a philosophy site, I don't think a question like "How can we formalize [some philosophical concept]?" is suitable question for cstheory, on the other hand asking for references for similar work would be OK IMHO. :) @Lev, as a user I am leaning towards closing as not-a-real-question ("It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form.") until Mohammad clarifies and improves it to a state that the question can be answered.  
> **username_6**: Also see this ongoing [meta discussion](http://meta.cstheory.stackexchange.com/questions/1251/how-to-deal-with-how-to-do-x-questions-where-x-is-a-very-high-level-software).  
> **username_0**: @username_6, The post clearly asks for references to works that address the weaknesses of Turing test. I'm asking for a better way to formalize the concept of machine (program) intelligence.  
> **username_4**: I voted +1 for this question and I like reading the comments and answers. I've taken a course in AI and it was just prolog programming with set theory, I read the AI book by Peter Norvig and Stuart Russel and that book just sums up basic concepts from other fields like probability theory, set theory and rule-based reasoning. I'm interested in self-modifying programs and the AI college course didn't even mention that and the Turing test was also not very formalized and like you say, it's subjective. Maybe you can look at patterns for cellular automata, machine learning and/or software bots.  

---

## 3 answers

### Answer by username_2 on 2011-08-14. Score: 8

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](http://turkistany.blogspot.com/2011/01/theory-of-computing-and-intelligent.html), 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](http://people.seas.harvard.edu/~valiant/evolvability-2008.pdf) 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](http://www.eecs.harvard.edu/~vitaly/papers/F_strongSQD_manu0614.pdf); taking "crossover" into account, you get [parallel correlational statistical queries](http://people.seas.harvard.edu/~varunk/docs/evolution-K11.pdf). 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.

> **Comments:**
> **username_0**: Thanks Lev. Aren't the rules that govern the evolution of programs expressable by some program (not necessarly halting)?  
> **username_2**: Sure. But I don't know what you're getting at...  
> **username_0**: You can not reduce intelligence in the evolutionary algorithm to evolution itself or randomness. The evolution mechanisms contain intelligence which can not be produced by evolution. I suggest that intelligence is conserved. A program can not be more intelligent than its creator.  
> **username_2**: 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...)  
> **username_0**: 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?  
> **username_4**: 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.  

---

### Answer by username_5 on 2011-08-15. Score: 5

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](http://cba.mit.edu/events/03.11.ASE/docs/VonNeumann.pdf), that it became public.

This paper was one of the precursors of the field of [Artificial Life](http://en.wikipedia.org/wiki/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](http://www.mitpressjournals.org/doi/abs/10.1162/artl.1993.1.1_2.75?journalCode=artl).

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.

> **Comments:**
> **username_5**: 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.  

---

### Answer by username_8 on 2011-08-15. Score: -1

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".

> **Comments:**
> **username_9**: 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.  

---

