# A Remarkable Property of Real-Valued Functions on Intervals of the Real Line

Today the 17 October 2019 I discussed a very remarkable fixed point theorem discovered by the Ukrainian mathematician Oleksandr Micholayovych Sharkovsky.

We recall that a periodic point of period $n\geq1$ for a function $f:X\to{X}$ is a point $x_n$ such that $f^n(x_n)=x_n$. With this definition, a periodic point of period $n$ is also periodic of period $m$ for every $m$ which is a multiple of $n$. If $f^n(x_n)=x_n$ but $f^k(x_n)\neq{x_n}$ for every $k$ from 1 to $n-1$, we say that $n$ is the least period of $x_n$.

Theorem 1. (Sharkovsky’s “little” theorem) Let $I\subseteq\mathbb{R}$ be an interval and let $f:I\to\mathbb{R}$ be a continuous function su. If $f$ has a point of least period 3, then it has points of arbitrary least period; in particular, it has a fixed point.

# Positive expansivity is impossible for reversible cellular automata

On Thursday 29 August 2019 I gave a talk about expansivity. I focused on positive expansivity and discussed a general statement which has a most remarkable consequence for cellular automata theory.

Find the talk on my personal blog HERE

# A crash course in subadditivity, part 1

Today, the 1st of March 2018, I gave what ended up being the first of a series of Theory Lunch talks about subadditive functions. The idea is to give an introduction to the subject, following Hille’s and Lind and Marcus’s textbooks, and stating an important theorem by the Hungarian mathematician Mihály Fekete; then, discuss some extensions to the case of many variables and their implications in the theory of cellular automata, referring to two of my papers from 2008, one of them with Tommaso Toffoli and Patrizia Mentrasti.

Let’s start from the beginning: Continue reading

# Nonuniversality in computation: A proof by semantic shift?

Today, the 8th of September 2016, we had a very interesting discussion about a theorem, due to Selim G. Akl, pointed to me in a tweet by Andy Adamatzky. Such theorem has, according to Akl, the consequence that the Church-Turing thesis, a basic tenet of theoretical computer science, is false. Of course, surprising statements require solid arguments: is Akl’s solid enough?

First of all, let us recall what the Church-Turing thesis is, and what it is not. Its statement, as reported by the Stanford Encyclopedia of Philosophy, goes as follows: Continue reading

# Second-order theories should not be taken lightly

First-order formal logic is a standard topic in computer science. Not so for second-order logic: which, though used the default in fields of mathematics such as topology and analysis, is usually not treated in standard courses in mathematical logic. For today’s Theory Lunch I discussed some classical theorems that hold for first-order logic, but not for second-order logic: Continue reading

# A concrete piece of evidence for incompleteness

On Thursday, the 25th of March 2015, Venanzio Capretta gave a Theory Lunch talk about Goodstein’s theorem. Later, on the 9th of March, Wolfgang Jeltsch talked about ordinal numbers, which are at the base of Goodstein’s proof. Here, I am writing down a small recollection of their arguments.

Given a base $b \geq 2$, consider the base- $b$ writing of the nonnegative integer $n = b^m \cdot a_m + b^{m-1} \cdot a_{m-1} + \ldots + b \cdot a_1 + a_0$

where each $a_i$ is an integer between $0$ and $b-1$. The Cantor base- $b$ writing of $n$ is obtained by iteratively applying the base- $b$ writing to the exponents as well, until the only values appearing are integers between $0$ and $b$. For example, for $b = 2$ and $n = 49$, we have $49 = 32 + 16 + 1 = 2^{2^2 + 1} + 2^{2^2} + 1$

and also $49 = 27 + 9 \cdot 2 + 3 + 1 = 3^3 + 3^2 \cdot 2 + 3 + 1$

Given a nonnegative integer $n$, consider the Goodstein sequence defined for $i \geq 2$ by putting $x_2 = n$, and by constructing $x_{i+1}$ from $x_i$ as follows: Continue reading

# Limit languages of cellular automata

At today’s Theory Lunch I discussed limit languages of cellular automata, and Lyman Hurd’s example of a CA whose limit language is not regular. I wrote about this on my other blog.

# Proving the beauty of a mind

In the previous Theory Lunch talk we introduced the notion of Nash equilibrium for games in normal form. Today, we went through the proof of Nash’s theorem of existence of mixed strategy Nash equilibria for finite games in normal form.

Let us recall the basic notions. In a game in normal form we have: Continue reading

# Playing with a beautiful mind

Today’s talk’s topic is an idea so important in game theory, and with so many applications in different fields including computer science, that it earned its discoverer, together with Reinhard Selten and John Harsanyi, the 1994 Nobel Memorial Prize in Economic Sciences.

To introduce this idea, together with other basic game-theoretic notions, we resort to some examples. Here goes the first one: Continue reading

# Many choices from few parameters

At the end of March I gave a talk about how to obtain a wide range of Bernoulli distributions with as few parameters as possible. This originates from the needs of simulations of complex systems with cellular automata machine. The solution I described comes from Mark Smith’s doctoral thesis, performed under the supervision of Tommaso Toffoli.

I wrote a post on this on my blog on cellular automata.