Tw. Goedla o niezupełności | Informatyka MIMUW

Dodatkowe informacje

Standardowy model arytmetyki to struktura ${\mathfrak N}=\langle
{\mathbb N},*^{\mathfrak N},+^{\mathfrak N},0^{\mathfrak N},1^{\mathfrak N},
\leq^{\mathfrak N}\rangle.$

Lemat o funkcji $\beta$ [Goedel]

Istnieje funkcja $\beta:{\mathbb N}\times{\mathbb N}\times{\mathbb N}\to{\mathbb N}$ taka, że:

Dla każdego ciągu $\bar{a}=a_0,\dots, a_r$ liczb naturalnych istnieją liczby naturalne $t,p$ (stanowiące kod ciągu $\bar{a}$ w sensie $\beta$) takie, że dla każdego $0\leq i\leq r$ zachodzi $\beta(t,p,i)=a_i.$
Istnieje formuła arytmetyki $\chi(x_1,x_2,x_3,x_4)$ taka, że
$({\mathfrak N},x_1:t,x_2:p,x_3:i,x_4:a)\models\chi$ wtw $\beta(t,p,i)=a.$

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$.

Wskazówka

Wskazówka do tego zadania jest szablonem do rozwiązań innych zadań z tych ćwiczeń.

Po lewej fragmenty formuły, po prawej ich sens. $\chi$ to formuła definiująca funkcję $\beta$.

$\exists n\exists t\exists p$	$n$ to liczba, której silnią ma być $x$, a $t,p$ to kod ciągu kolejnych silni o długości $n+1$
$[\chi(t,p,0,1)$	w ciągu na pozycji $0$ jest $1$
$\wedge\forall i(i< n\to(\exists a\chi(t,p,i,a)\land\chi(t,p,i+1,a*(i+1)))$	w ciągu na pozycji $i+1$ jest liczba $i+1$ razy większa od poprzedniej
$\wedge\chi(t,p,n,x)$]	w ciągu na pozycji $n$ jest $x$,czyli $x=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$.

Wyjaśnienie

Polecenie brzmi "napisać" i o to właśnie chodzi. Nie wystarczy wykazać, że takie zdanie istnieje.
Dlaczego to nie jest objętne?

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$.

Wyjaśnienie

Automat może być niedeterministyczny.
Można sobie wybrać, czy rozwinięcie binarne $(n)_2$ czytamy od nastarszego czy od najmłodszego bitu.

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$.

Wyjaśnienie

Automat z licznikem to automat ze stosem, w którym alfabet stosu jest jednoelementowy.
Zakładamy akceptację przez stan, automat może być niedeterministyczny i wykonywać $\varepsilon$-ruchy.
Można sobie wybrać, czy rozwinięcie binarne $(n)_2$ czytamy od nastarszego czy od najmłodszego bitu.

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$.

Wyjaśnienie

Zakładamy akceptację przez stan, automat może być niedeterministyczny i wykonywać $\varepsilon$-ruchy.
Można sobie wybrać, czy rozwinięcie binarne $(n)_2$ czytamy od nastarszego czy od najmłodszego bitu.

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$.

Wyjaśnienie

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$.

Wyjaśnienie

Zakładamy akceptację przez stan, maszyna $M$ może być niedeterministyczna.
Można sobie wybrać, czy rozwinięcie binarne $(n)_2$ czytamy od nastarszego czy od najmłodszego bitu.

\(\exists n\exists t\exists p\)	\(n\) to liczba, której silnią ma być \(x\), a \(t,p\) to kod ciągu kolejnych silni o długości \(n+1\)
\([\chi(t,p,0,1)\)	w ciągu na pozycji \(0\) jest \(1\)
\(\wedge\forall i(i< n\to(\exists a\chi(t,p,i,a)\land\chi(t,p,i+1,a*(i+1)))\)	w ciągu na pozycji \(i+1\) jest liczba \(i+1\) razy większa od poprzedniej
\(\wedge\chi(t,p,n,x)\)]	w ciągu na pozycji \(n\) jest \(x\),czyli \(x=n!\).