What are some topics in computability?

[mathmari]

Hello!

I am taking the course Computability and at the end of the semester each student will have a presentation about a topic that is related to Computability.

Could you give some examples of topics?? (Wondering)

 

[Evgeny.Makarov]

Here are the topics that I offered at the end of a course on Theory of Computation.

• The original Turing's paper where he introduced Turing machines and proved that the halting problem is undecidable [1, 2].
• Matiyasevich's solution to the 10th Hilbert's problem.
• Quantum computations.
• Arithmetical hierarchy,
• Kolmogorov complexity.
• Probabilistic computations.
• Approximate solutions of NP-complete problems.
• Interactive proof systems.
• Cryptography.

[1] On computable numbers, with an application to the Entscheidungsproblem.
Proceedings of the London Mathematical Society., s2-42 (1), 1937.
URL: On Computable Numbers, with an Application to the Entscheidungsproblem.

[2] Turing A. On computable numbers, with an application to the Entscheidungsproblem: A correction.
Proceedings of the London Mathematical Society, s2-43 (1), 1938.
URL: Sign In

Edit: The links are parsed despite checking off the "Automatically parse links in text" box. I give up.

 

[mathmari]

How is Cryptography related to Computability?? (Wondering)

 

[Evgeny.Makarov]

How is Cryptography related to Computability??

One needs to prove that the operation of decrypting has a certain lower bound on complexity. I agree, this is more about computational complexity rather than computability (the study of what is computable), but both of these topics are usually a part of a course on the theory computation.

 

[mathmari]

While I was looking for topics I came across the Church-Turing-Thesis.

Could you give me some information about that?? Is this related to Computability?? Is this a good topic for a presentation?? (Wondering)

Could you also give me some information about "Approximate solutions of NP-complete problems"?? (Wondering)

 

[Evgeny.Makarov]

Why are you using several question marks? And why are you using smilies after serious questions? Does this mean I should take them with a grain of salt?

While I was looking for topics I came across the Church-Turing-Thesis.

Could you give me some information about that?? Is this related to Computability?? Is this a good topic for a presentation??

Yes, it is directly related to computability. You could start by reading Wikipedia. This thesis is an statement about the informal, intuitive concept of computability; thus, it cannot be proved. But it is given support by theorems that establish equivalence of different models of computation: Turing machines, recursive functions, lambda calculus, Markov algorithms and so on. In a presentation, you could either talk about those theorems or about the philosophical reasons for the thesis. I believe one of Turing's papers, maybe the one I quoted, discusses why any physically realizable universal computing device should resemble Turing machine. At first glance, Turing machine may seem somewhat restricted and there is a possibility that a more complicated and powerful machine can be built. But the article shows that Turing machine already has the features that you can expect from any other computer.

Could you also give me some information about "Approximate solutions of NP-complete problems"??

I recommend referring to the https://driven2services.com/staging/mh/index.php?posts/65491/ I cited previously.

 

[mathmari]

One needs to prove that the operation of decrypting has a certain lower bound on complexity. I agree, this is more about computational complexity rather than computability (the study of what is computable), but both of these topics are usually a part of a course on the theory computation.

OK... This semester I am taking the course of Cryptography. Do you think it is a good idea to take this topic or would it be better if I had taken Cryptography in the past so that I would haver seen the whole subject and then do a presentation about that? How much knowledge is required? Do you think this one of the difficult or the easy topics?

 

[Nono713]

OK... This semester I am taking the course of Cryptography. Do you think it is a good idea to take this topic or would it be better if I had taken Cryptography in the past so that I would haver seen the whole subject and then do a presentation about that? How much knowledge is required? Do you think this one of the difficult or the easy topics?

It depends what the subject is about exactly. If it's "introduction to cryptography" it will probably have basically nothing to do with computability and will be more about the older pen and paper ciphers, using group theory and linear algebra to break them and so on, with maybe a chapter at the end touching on public-key systems and their relation to various P/NP problems (such as the knapsack cryptosystem). If it's something more advanced, then you'll encounter formal definitions of security and formal computational hardness proofs, composability, security conditional on hardness assumptions and so on.

 

[mathmari]

It depends what the subject is about exactly. If it's "introduction to cryptography" it will probably have basically nothing to do with computability and will be more about the older pen and paper ciphers, using group theory and linear algebra to break them and so on, with maybe a chapter at the end touching on public-key systems and their relation to various P/NP problems (such as the knapsack cryptosystem). If it's something more advanced, then you'll encounter formal definitions of security and formal computational hardness proofs, composability, security conditional on hardness assumptions and so on.

Ok... :)

- - - Updated - - -

What do you think about the topics of program verification and circuit complexity?

 

[Nono713]

I don't have any experience in either but it sounds cool. If it excites you, do it!

 

[mathmari]

I am still looking for a topic... Now I found Ackermann’s Function. What do you think about this topic? Could you give me some information about it?

 

[Evgeny.Makarov]

What do you think about the topics of program verification and circuit complexity?

Personally, program verification is one of my favorite topics, not to mention its importance in the real world, even though it is still developing. I like dealing with high-level programming languages, and seeing formal methods apply to programs that I could actually have written in order to prove them correct is cool. It is both mathematical and practical.

I don't have much experience with circuit complexity, but to me it is the opposite: very low level. I don't get excited about ANDs and ORs the same way I get excited about programs in Java, Haskell or Prolog. But it's as valid CS and math topic as any. And it may be applicable to chip design.

I forgot that you are looking for a presentation topic, not a course to take. In this case the commitment is significantly less.

I am still looking for a topic... Now I found Ackermann’s Function. What do you think about this topic? Could you give me some information about it?

Ackermann’s function is a recursive function of two arguments that grows very fast. The first argument gives the level, so ti speak: first it's adding 1, then addition, then multiplication, exponentiation, iterated exponentiation and so on. As the first argument increases, it becomes faster and faster growing. Eventually it surpasses every so called primitive recursive functions (PRF). The class of PRF includes almost all functions used in real life, so Ackermann’s function is an examples of something different. Other than that, it is not really interesting, as far as I know.

 

[mathmari]

Ackermann’s function is a recursive function of two arguments that grows very fast. The first argument gives the level, so ti speak: first it's adding 1, then addition, then multiplication, exponentiation, iterated exponentiation and so on. As the first argument increases, it becomes faster and faster growing. Eventually it surpasses every so called primitive recursive functions (PRF). The class of PRF includes almost all functions used in real life, so Ackermann’s function is an examples of something different.

What book would you recommend me for this topic? Are there any survey articles?

 

[Evgeny.Makarov]

What book would you recommend me for this topic? Are there any survey articles?

I don't have anything off the top of my head. You should start with primitive recursive functions. Look at Wikipedia references for both topics. Math Stack Exchange has some recommendations.

In fact, if I remember correctly, a classic book, in particular, on PRF is "Recursive Functions" by Rózsa Péter. It should talk about Ackermann function, but I don't have it at the moment to check.

 

[mathmari]

• Quantum computations.
• Arithmetical hierarchy,
• Kolmogorov complexity.

Are these topics suitable for a master thesis?

Have you heard of the Speed-Up theorem?