Informatyka MIMUW

Zad. 1
Napisać formułę $\varphi(x)$ nad sygnaturą arytmetyki orzekającą, że $x$ jest silnią pewnej liczby, tzn. że dla wszystkich wartościowań $v:X\to{\mathbb N}$
$({\mathfrak N},v)\models\varphi$ wtw $v(x)$ jest postaci $n!$ dla pewnego $n$.

Zad. 2
Napisać formułę $\varphi(x,y)$ nad sygnaturą arytmetyki definiującą funkcję $y=\lfloor \log_2 x\rfloor,$ tzn. taką, że dla wszystkich wartościowań $v:X\to{\mathbb N}$
$({\mathfrak N},v)\models\varphi$ wtw $v(y)=\lfloor \log_2 v(x)\rfloor.$

Zad. 3
Napisać formułę $\varphi(x,y,z)$ nad sygnaturą arytmetyki definiującą funkcję $y=\lfloor \sqrt[z]{x}\rfloor,$ tzn. taką, że dla wszystkich wartościowań $v:X\to{\mathbb N}$

${\mathfrak N}\models\varphi[v]$ wtw} $v(y)=\lfloor (v(x))^{\frac{1}{v(z)}}\rfloor.$

Zad. 4
Znaleźć formułę $\varphi(x,y)$ stwierdzającą w standardowym modelu arytmetyki, że $y$ jest największą liczbą, będącą potęgą liczby pierwszej, która dzieli $x,$ czyli taką, że dla wszystkich wartościowań $v:X\to{\mathbb N}$

$({\mathfrak N},v)\models\varphi$ wtw $v(y)$ jest największą potęgą liczby pierwszej, która jest dzielnikiem $v(x)$.

Zad. 5
Liczba naturalna $n$ jest doskonała gdy jest równa sumie wszystkich swoich dzielników różnych od $n.$ Np. $6=1+2+3$ jest doskonała.

Napisać formułę $\varphi(x)$ nad sygnaturą arytmetyki taką, że dla wszystkich wartościowań $v:X\to{\mathbb N}$

$({\mathfrak N},v)\models\varphi$ wtw $v(x)$ jest doskonała.

Zad. 6
Napisać formułę $\varphi(x)$ nad sygnaturą arytmetyki definiującą relację ,,$x$ ma nieparzystą ilość cyfr w rozwinięciu dziesiętnym'', tzn. taką, że dla wszystkich wartościowań $v:X \to{\mathbb N}$ zachodzi równoważność $({\mathfrak N},v)\models\varphi$ wtw $v(x)$ ma nieparzystą ilość cyfr w rozwinięciu dziesiętnym.

Zad. 7
Hipoteza Collatza (albo inaczej hipoteza $3k+1$) orzeka, że następujący prosty program $\pi$ zatrzymuje się dla każdej wartości początkowej zmiennej $k$:

while k<>1 do
   if k mod 2=0 
      then k:=k div 2
      else k:=3*k+1;

Hipoteza ta dotąd nie została ani udowodniona ani obalona i ma reputację niezmiernie trudnego problemu.
Napisać zdanie $\varphi$ nad sygnaturą arytmetyki orzekające, że hipoteza Collatza jest prawdziwa, tzn.
${\mathfrak N}\models\varphi$ wtw $\pi$ zatrzymuje się dla każdej danej wejściowej $k$.

Zad. 8
Rozważamy struktury $\mathfrak{N}_f$ postaci $\langle\mathbb{N},+,*,0,1,f\rangle$, gdzie dla uproszczenia symbol jednoargumentowej funkcji $f$ oznacza także jej interpretację, a pozostałe symbole funkcji są interpretowane w standardowy sposób.

Napisać zdanie $\varphi$ nad sygnaturą arytmetyki wzbogaconą o $f$ takie, że dla każdej funkcji $f:\mathbb{N}\to{\mathbb N}$ zachodzi

${\mathfrak N}_f\models\varphi$ wtw $f$ jest wielomianem o współczynnikach naturalnych.

Zad. 9
Dla danego automatu skończonego $A$ nad alfabetem $\{0,1\}$ napisać formułę $\varphi(x)$ taką, że
${\mathfrak N},x:n\models\varphi$ wtw $A$ akceptuje słowo $(n)_2$.

Zad. 10
Dla danego automatu z licznikiem $A$ nad alfabetem $\{0,1\}$ napisać formułę $\varphi(x)$ taką, że
${\mathfrak N},x:n\models\varphi$ wtw $A$ akceptuje słowo $(n)_2$.

Zad. 11
Dla danego automatu ze stosem $A$ nad alfabetem $\{0,1\}$ i alfabetem stosu $\{0,1\}$ napisać formułę $\varphi(x)$ taką, że
${\mathfrak N},x:n\models\varphi$ wtw $A$ akceptuje słowo $(n)_2$.

Zad. 12
Dla danego automatu z dwoma stosami $A$ nad alfabetem $\{0,1\}$ i alfabetem stosów $\{0,1\}$ napisać formułę $\varphi(x)$ taką, że
${\mathfrak N},x:n\models\varphi$ wtw $A$ akceptuje słowo $(n)_2$.

Zad. 13
Dla danej maszyny Turinga $M$ nad alfabetem $\{0,1\}$ i z alfabetem taśmy $\{0,1\}$ napisać formułę $\varphi(x)$ taką, że
${\mathfrak N},x:n\models\varphi$ wtw $M$ akceptuje słowo $(n)_2$.