\documentclass[fleqn,11pt,a4paper]{article}

\usepackage{a4wide}
\usepackage{amsmath}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}

\usepackage{amsfonts}

\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{enumerate}
\usepackage{setspace}
\parskip .7mm

\binoppenalty=10000 
\relpenalty=10000
\hyphenpenalty=8000
\exhyphenpenalty=1000



\everymath{\displaystyle}

\begin{document}


\centerline{\Large Azar, Algoritmos y Aut\' omatas}
\medskip


\centerline{Ejercicios para entregar}
\bigskip

\noindent
{\bf Definición:}  Una secuencia infinita $x$ en el afabeto $\{0,1\}$ es de Bruijn si cumple 
que, 
o bien  para todo $n$ par, $x[1,2^n]$ es de Bruijn de orden $n$ , 
o bien  para todo $n$ impar, $x[1,2^n]$ es de Bruijn de orden $n$.
\medskip


\noindent
{\bf Ejercicio 0}


\noindent
Demostrar que las secuencias de Bruijn infinitas existen paar el alpfabeto de dos símbolos.
\bigskip




\noindent
{\bf Ejercicio 1}


\noindent
Demostrar que la concatenaci\'on de secuencias de Bruijn de orden sucesivo es normal.
\bigskip







\noindent
{\bf Ejercicio 2}
%\\
%
%Definici\' on: Fijemos el alfabeto $A$. Una secuencia  $x$  es 
%$(n,k)$-perfecta si tiene longitud  $k |A|^n$  y, cada palabra de longitud $n$ 
%ocurre exactamente $k$ veces en  la secuencia circular de $x$ en 
%posiciones que son diferentes modulo $k$, 
%para cualquier convenci\' on del punto inicial. 
%\medskip


%Referencia: N. Alvarez, V. Becher, P. Ferrari and S. Yuhjtman. "Perfect necklaces", Advances of Applied Mathematics 80:48--61, 2016. 
%\\
%{\tt https://www-2.dc.uba.ar/staff/becher/papers/abfy.pdf}
%\bigskip
%
\noindent
Demostrar que la concatenaci\' on de secuencias  $(2n,2n)-$perfectas 
 para $n=1,2,3, \ldots$  es una secuencia normal.
\bigskip



\noindent
{\bf Ejercicio 3}
\\Dar la demostraci\'on del teorema de Piatetski-Shapiro para ocurrencias alineadas.
\bigskip


\noindent
{\bf Ejercicio 4}

\noindent
Sea  $x$ una secuencia $(2^m,2^m)$-perfecto anidado. 
Mostrar que, para todo $N$, para todo $\ell\leq m$, 
\[
\Delta_{\ell,N}(x)\leq O\big(2^{2m}/ N\big).
\]
¿Pod\'es comentar algo sobre la cota inferior de $\Delta_{\ell,N}(x)$?
%Si  $\ell\leq\log \log N$ entonces podemos tomar  $N_\ell=1$.
{\bf Ayuda:}
Fijemos $N$ entre $1$ y $|x|= 2^{m}b^{2^{m}}$.
Sean   $N_0$ y   $n_1, \ldots n_{2^{m}-1}$ 
enteros tales que
$0\leq N_0< 2^m$,
   $n_i\in \{0,..., b-1\}$  y 
\[
 N=  2^m \left(\sum_{i=0}^{2^{m}-1} n_i b^i  \right)+ N_0.
\]
Es decir, escribimos  $N$ como 
 la suma de las longitudes de  $n_i$ secuencias  $(i, 2^m)$-perfectas anidadas
para   $i=0,\ldots,2^{m-1}$ m\'as $N_0$, con $0\leq N_0< 2^m$,
\medskip

\centerline{$x[1,N]$
 =
\fbox{$n_0  2^m b^0\ |  \ n_1 2^m b^{1} | \ n_2 2^m b^2 | \ \ldots | \ n_{2^{m}-1} 2^m b^{2^{m}-1} \ | \ N_0 \hspace{0.5cm}$}}


\noindent
{\bf Ejercicio 5}
\\Adaptar el algoritmo de Turing para generar un n\'umero normal en base 2 y base 5, y expresar su expansion fraccionaria en base 5.
\bigskip

\noindent
{\bf Ejercicio 6}
\\
Adaptar el algoritmo polinomial BHS para general un n\'umero normal en base 2 y 3,y expresar su expansion fraccionaria en base 3.
\bigskip






\noindent
{\bf Ejercicio 7}
\\
Dada una secuencia $a_1 a_2 \ldots$ donde los $a_i$ son s\'imbolos del alfabeto,
$tres(x)$ es la subsecuencia de $x$ que se obtiene de tomar los s\' imbolos 
en las posiciones múltiplos de tres de $x$
Es decir,  $tres(x)=a_3 a_6 a_9 \ldots $.
\medskip

Demostrar que si $x$ es una secuencia  normal  entonces   la subsecuencia   
$tres(x)$  es normal.
\bigskip


\noindent
{\bf Ejercicio 8}
\\Indicar  una forma de selecci\' on de  subsecuencias tal que no siempre preserva normalidad. 
  Dar un ejemplo de una secuencia normal donde no se preserve.
\bigskip



\noindent
{\bf Ejercicio 9}
\\
Demostrar que los n\'umeros Martin-L\"of aleatorios  son normales.
\bigskip

\noindent
{\bf Ejercicio 10}
\\
Dar un algoritmo que permite computar  $\Omega$ 
 con un or\' aculo para el problema de la detenci\' on.
\bigskip

\noindent
{\bf Ejercicio 11}
Demostrar  dando un test que estos  no son  Martin-L\"of aleatorios:
\begin{enumerate}
\item  La secuencia  caracter\'istica de la detenci\'on.

\item El n\' umero  $\beta$ de Turing.

\item El n\' umero  $\Omega'$  que resulta de intercalar $0$s entre los bits de $\Omega$. 
Es decir, si $\Omega = b_1 b_2 b_3 \ldots$ entonces 
$\Omega'= b_1 0 b_2 0 b_3 0 \ldots $. 
\end{enumerate}

\noindent
{\bf Ejercicio 12}

\begin{enumerate}

\item Demostrar que el n\'umero $(1-\Omega)$ es aleatorio.


\item Para todo  conjunto $X$ infinito c.e. pero no computable
\[\sum_{x\in X} 2^{-|x|}
\]
 es Martin-L\"of aleatorio.


\item El n\'umero $\Omega_0$ que resulta de anteponer mil $0$s delante de $\Omega$

\item Demostrar  que $\sum_{\mbox{\tiny palabra } s} 2^{-K(s)}$
  es  computablemente aproximable desde abajo  y Martin L\"of  aleatorio.
\end{enumerate}


\noindent
{\bf Ejercicio 13}
\\Dar un test de Martin L\"of  que contenga a los n\' umeros decimales cuya expansion decimal no contiene el $7$ .
\bigskip

\noindent
{\bf Ejercicio 14 } (opcional)
\\Demostrar que ning\' un numero de Liouville es Martin L\"of aleatorio.
\bigskip

\noindent
{\bf Ejercicio 15 } (por definir, sobre tests de aleatoriedad de secuencias finitas)
\bigskip

%\noindent
%{\bf Ejercicio 15 (opcional)}
%\\Construir una secuencia infinita  $a_1a_2\ldots$  tal que sea normal y para todo $n$, $a_n =a_{3n}$.
%\bigskip


\end{document}
