What are some alternative topics for a Theory of Computation presentation?

[evinda]

Hello! (Wave)

Could you suggest me other topics for a presentation in Theory of Computation other than the ones that were suggested by Evgeny Makarov to mathmari in this post: http://mathhelpboards.com/chat-room-9/computability-14368.html#post67959 ?

Is for example the topic [m]Algorithmic randomness[/m] good for a presentation? What is it about? Could you give me some informations about it?

 

[Evgeny.Makarov]

Is for example the topic [m]Algorithmic randomness[/m] good for a presentation?

Yes, it's a good topic.

What is it about? Could you give me some informations about it?

I am not a specialist, but I believe it is closely related to Kolmogorov complexity, which is the study of complexity and randomness of individual finite objects rather than probability space as a whole. Another creator of this field is Gregory Chaitin, who has a popular book "Meta Math!: The Quest for Omega". You can read about algorithmic randomness here.

 

[evinda]

So Algorithmic randomness is related to probability theory, right?

Is there maybe also a topic related to Set theory?

 

[Evgeny.Makarov]

So Algorithmic randomness is related to probability theory, right?

Yes. In particular, it's related to the question, Can an object (like a sequence of symbols) be deterministically generated and yet random?

Is there maybe also a topic related to Set theory?

There is Finite model theory, though it is not so much about sets as about structured sets, e.g., graphs. FMT has many applications in computer science. There is also Effective descriptive set theory.

 

[evinda]

Yes. In particular, it's related to the question, Can an object (like a sequence of symbols) be deterministically generated and yet random?

A ok...

There is Finite model theory, though it is not so much about sets as about structured sets, e.g., graphs. FMT has many applications in computer science. There is also Effective descriptive set theory.

These topics sound interesting. I will think about it.
To what other fields could we relate computability theory?

 

[Evgeny.Makarov]

To what other fields could we relate computability theory?

You can look at chapter 10 in the Sipser's book, though some topics there have already been mentioned in these threads.

 

[evinda]

What do you think of the topic inductive inference? Could you give me some information about it?

 

[Evgeny.Makarov]

I am not sure in what sense you are using the phrase "inductive inference". It may refer simply to "inductive reasoning", which is a concept from the philosophy of science. It may have precise mathematical meanings, but I am not sure I encountered this term literally. For an example of possible precise meanings, a simple inference (provability relation) in propositional or predicate logic can be viewed as an inductive predicate because it has a recursive (or inductive) definition.

 

[evinda]

I have found a pdf about it in german with title Algorithmic Studying with the method of inductive inference, the source of which is the book [m]Angluin, D. and Smith, C. (1983). Inductive inference: Theory and methods. Computing Surveys, 15(3):237--269[/m]. But I haven't found the book online.

 

[Evgeny.Makarov]

I have found a pdf about it in german with title Algorithmic Studying with the method of inductive inference, the source of which is the book [m]Angluin, D. and Smith, C. (1983). Inductive inference: Theory and methods. Computing Surveys, 15(3):237--269[/m]. But I haven't found the book online.

This is not a book, but an article published in the journal ACM Computing Surveys. There is a link to this article on the Wikipedia page about Ray Solomonoff's theory of inductive inference. Solomonoff is one of the inventors of Kolmogorov complexity along with Kolmogorov himself and Gregory Chaitin.

 

[evinda]

This is not a book, but an article published in the journal ACM Computing Surveys. There is a link to this article on the Wikipedia page about Ray Solomonoff's theory of inductive inference. Solomonoff is one of the inventors of Kolmogorov complexity along with Kolmogorov himself and Gregory Chaitin.

A ok. I read about it. Do you think that it is a good topic for a presentation? Is the topic difficult?

 

[Evgeny.Makarov]

Do you think that it is a good topic for a presentation?

Yes, I think it is interesting.

Is the topic difficult?

I don't know, I have not studied it.

 

[evinda]

Yes, I think it is interesting.

Yes, I think so too... Maybe I will choose this topic. (Smile)

What do you think of the concept of a Quine as a topic for the presentation?

 

[Evgeny.Makarov]

What do you think of the concept of a Quine as a topic for the presentation?

I did not know that programs that print their own texts are called quines. That would be an interesting topic for a presentation if it is tied to theory, such as Kleene's fixed point theorem and Gödel's incompleteness theorem (more precisely, the fixed-point lemma). For example, the Wikipedia page has a link "A Java Quine built straight from Kleene's fixed point theorem, composition and s-n-m".

 

[evinda]

I suggested the topic quines, but the prof doesn't agree.

Now he told us that it doesn't have to do something with Computability.
It should be any scientifical interesting and wide topic.
Do you have any other suggestions for me?

 

[Evgeny.Makarov]

Now he told us that it doesn't have to do something with Computability.
It should be any scientifical interesting and wide topic.

A university program in mathematics consists of several dozens of courses. Each course can offer dozens of possible project topics. Finally, a typical university offers dozens of programs related to science besides mathematics. Do you really think it is possible to meaningfully discuss the choice of one topic without additional constraints?

 

[evinda]

A university program in mathematics consists of several dozens of courses. Each course can offer dozens of possible project topics. Finally, a typical university offers dozens of programs related to science besides mathematics. Do you really think it is possible to meaningfully discuss the choice of one topic without additional constraints?

Yes, I agree that it's not possible...
Do you think that boolean functions would be a good topic?

 

[Evgeny.Makarov]

Do you think that boolean functions would be a good topic?

Yes. This topic has both simple and complicated problems. For example, there is Posts's theorem, which gives a necessary and sufficient condition saying when a system of logical connectives is functionally complete. In Russia this theorem is often included in first-year discrete math courses. Also see the link to Post's lattice. One can ask for an analog of this theorem for 3- or higher-valued logics. One can also study logic circuits and ask how many logic gates are necessary to implement every Boolean function of $n$ arguments.

 

[evinda]

Could you suggest me a possible structure how the presentation could look like?
Also could you suggest me a book where I could read about that topic?

 

[Evgeny.Makarov]

Could you suggest me a possible structure how the presentation could look like?

From introduction of Boolean functions to Posts's criterion.

Also could you suggest me a book where I could read about that topic?

Post criterion for completeness is described, in particular, in the following books.

Victor W. Marek. Introduction to mathematics of satisfiability. Chapman and Hall (2009). Section 5.5.

S. V. IAblonskii. Introduction to discrete mathematics. 1989. Chapter 1. This textbook is used in Russia.

I am sure there are many more books.

 

[evinda]

Thank you! (Smile) I will take a look at the books.
Could you maybe also suggest me a good presentation topic related to the field Algorithms and complexity?

 

[Evgeny.Makarov]

Any topic from the following books will do.

Aho, Hopcroft, Ullman. The design and analysis of computer algorithms.

Purdom, Brown. The Analysis of Algorithms.

The first book is classics. I like the second book because besides the main topic it contains a lot of mathematical background, such as a proof of Stirling's approximation.

 

[evinda]

What do you think of algebraic complexity as a presentation topic?

 

[Evgeny.Makarov]

What do you think of algebraic complexity as a presentation topic?

I am not familiar with this topic, but I think it would work as a presentation topic.

 

[evinda]

I am not familiar with this topic, but I think it would work as a presentation topic.

Ok, I will think about it.

- - - Updated - - -

S. V. IAblonskii. Introduction to discrete mathematics. 1989. Chapter 1. This textbook is used in Russia.

Is there an online version of this book? Because I haven't found it yet.

 

[Evgeny.Makarov]

Amazon only has a hardcover copy. I would not chase after this particular book. I am sure there are many popular English textbooks that cover complete systems of Boolean functions.

 

[evinda]

Ok.
I have also thought about further topics.
What do you think of the following two as presentation topics?
[m]Complexity of the geography game[/m] or [m]Modeling of music network supported by the computer [/m]

 

[Evgeny.Makarov]

I am not familiar with them.

I think this thread has enough information to choose a topic for a presentation. I don't want to turn the choice of topic into a project of its own.