Properti yang dapat ditentukan dari real yang dapat dihitung

Ya, teorema Rice untuk real berlaku di setiap versi wajar real yang dapat dihitung.

Pertama-tama saya akan membuktikan teorema dan konsekuensi wajar tertentu, dan menjelaskan apa hubungannya dengan komputabilitas nanti.

Teorema: Misalkan adalah peta dan dua realals sehingga dan . Kemudian ada urutan Cauchy sedemikian rupa sehingga untuk semua . $p : \mathbb{R} \to \{0,1\}$ $a, b \in \mathbb{R}$ $p(a) = 0$ $p(b) = 1$ $(x_i)_i$ $p(\lim_i x_i) \neq p(x_j)$ $j \in \mathbb{N}$

Bukti. Kami membangun urutan pasangan real sebagai berikut: Perhatikan itu untuk semua : $(y_i, z_i)_i$

\begin{aligned} (y_{0}, z_{0}) & = (a, b) \\ (y_{i + 1}, z_{i + 1}) & = {\begin{cases} (y_{i}, (y_{i} + z_{i}) / 2) & if p ((y_{i} + z_{i}) / 2) = 1 \\ ((y_{i} + z_{i}) / 2, z_{i}) & if p ((y_{i} + z_{i}) / 2) = 0 \end{cases} \end{aligned}

$\begin{align*} (y_0, z_0) &= (a, b) \\ (y_{i+1}, z_{i+1}) &= \begin{cases} (y_i, (y_i + z_i)/2) & \text{if $p((y_i + z_i)/2) = 1$} \\ ((y_i + z_i)/2, z_i) & \text{if $p((y_i + z_i)/2) = 0$} \\ \end{cases} \end{align*}$

i \in N

$i \in \mathbb{N}$

$p(y_i) = 0$ dan $p(z_i) = 1$
$|z_i - y_i| = |b - a| \cdot 2^{-i}$
$|y_{i+1} - y_i| \leq |b - a| \cdot 2^{-i}$
$|z_{i+1} - z_i| \leq |b - a| \cdot 2^{-i}$

Dengan demikian urutan dan adalah Cauchy dan mereka bertemu ke titik umum . Jika maka kita ambil , dan jika maka kita ambil . $(y_i)_i$ $(z_i)_i$ $c = \lim_i y_i = \lim_i z_i$ $p(c) = 0$ $(x_i)_i = (z_i)_i$ $p(c) = 1$ $(x_i)_i = (y_i)_i$ $\square$

Konsekuensi: Misalkan dan dua realals sehingga dan . Kemudian setiap mesin Turing dapat berjalan selamanya atau tidak selamanya. $p : \mathbb{R} \to \{0,1\}$ $a, b \in \mathbb{R}$ $p(a) = 0$ $p(b) = 1$

Bukti. Menurut teorema, ada urutan Cauchy sedemikian rupa sehingga untuk semua . Tanpa kehilangan umum kita dapat mengasumsikan bahwa dan . $(x_i)_i$ $p(x_j) \neq p(\lim_i x_i)$ $j \in \mathbb{B}$ $p(x_j) = 1$ $p(\lim_i x_i) = 0$

Biarkan menjadi mesin Turing. Tentukan urutan oleh Urutannya didefinisikan dengan baik karena kita dapat mensimulasikan langkah hingga dan memutuskan apakah telah berhenti atau tidak dalam banyak langkah itu. Selanjutnya, amati bahwa adalah urutan Cauchy karena adalah urutan Cauchy (kita biarkan ini sebagai latihan). Biarkan . Baik atau : $T$ $y_i$

y_{i} = {\begin{cases} x_{j} & if T halts in step j and j \leq i \\ x_{i} & if T does not halt within i steps \end{cases}

$y_i = \begin{cases} x_j & \text{if $T$ halts in step $j$ and $j \leq i$}\\ x_i & \text{if $T$ does not halt within $i$ steps} \end{cases}$

T

$T$

i

$i$

(y_{i})_{i}

$(y_i)_i$

(x_{i})_{i}

$(x_i)_i$

z = lim_{i} y_{i}

$z = \lim_i y_i$

p (z) = 0

$p(z) = 0$

p (z) = 1

$p(z) = 1$

jika maka berjalan selamanya. Memang, jika berhenti setelah langkah , maka kita akan memiliki , dan akan bertentangan dengan . $p(z) = 0$ $T$ $j$ $z = x_j$ $p(z) = p(x_j) = 1$ $p(z) = 0$
jika maka tidak berjalan selamanya. Memang, jika ya, maka kita akan memiliki , dan , bertentangan dengan . $p(z) = 1$ $T$ $z = \lim_i x_i$ $p(z) = p(\lim_i x_i) = 0$ $p(z) = 0$ $\square$

Sekarang kita bisa menjelaskan mengapa ini memberi kita teorema Rice untuk bilangan real. Buktinya konstruktif, karena itu menghasilkan prosedur yang dapat dihitung. Ini berlaku untuk model komputasi mana pun dan struktur perhitungan real apa pun yang pantas disebut demikian. Bahkan, Anda dapat kembali dan membaca buktinya sebagai instruksi untuk membangun sebuah program - semua langkahnya dapat dihitung.

Jadi, jika kita memiliki peta computable dan computable sedemikian rupa sehingga dan , maka kita dapat menerapkan prosedur komputasi yang timbul dari bukti konstruktif teorema dan akibat wajar untuk membuat oracle Menghentikan. Tetapi oracle Halting tidak ada, oleh karena itu, setiap peta yang dapat dihitung adalah konstan. $p : \mathbb{R} \to \{0,1\}$ $a, b \in \mathbb{R}$ $p(a) = 0$ $p(1) = 1$ $p : \mathbb{R} \to \{0,1\}$

Tambahan: Ada juga pertanyaan tentang apakah teorema Rice terkait dengan keterhubungan real. Ya, pada dasarnya pernyataan bahwa real terhubung.

Pertama-tama mari kita amati bahwa peta kontinu (kita mengambil topologi diskrit pada ) sesuai dengan sepasang clopen disjoint (tertutup dan terbuka) mengeset sehingga . Memang, ambil dan . Karena kontinu dan dan terbuka, dan akan terbuka, menguraikan, dan mereka jelas menutupi semua . Sebaliknya, setiap pasangan dari clopens terpisah yang menutupi menentukan peta kontinu $p : X \to \{0,1\}$ $\{0,1\}$ $U, V \subseteq X$ $U \cup V = X$ $U = p^{-1}(\{0\})$ $V = p^{-1}(\{1\})$ $p$ $\{0\}$ $\{1\}$ $U$ $V$ $X$ $(U,V)$ $X$ $p : X \to \{0,1\}$ yang memetakan elemen ke dan elemen ke . $U$ $0$ $V$ $1$

Dari sini kita belajar bahwa ruang terputus jika, dan hanya jika, ada peta kontinu dan sehingga dan (kita perlu dan sehingga kita mendapatkan dekomposisi tidak sepele ). Ada cara lain untuk mengatakan hal yang sama: spasi terhubung jika, dan hanya jika, semua peta berkelanjutan konstan. $X$ $p : X \to \{0,1\}$ $a, b \in X$ $p(a) = 0$ $p(1) = b$ $a$ $b$ $X$ $X$ $X \to \{0,1\}$

Dalam matematika yang dapat dihitung, kami memiliki teorema dasar: setiap peta yang dapat dihitung adalah kontinu . Jadi, selama kita berada dalam bidang objek yang dapat dihitung, teorema Rice sebenarnya menyatakan bahwa ruang tertentu terhubung. Dalam kasus teorema Rice klasik, spasi yang dimaksud adalah ruang fungsi parsial yang dapat dihitung . $\mathbb{N} \to \mathbb{N}$

Andrej Bauer
sumber

Terima kasih! Ini yang saya cari. Adakah gagasan tentang pertanyaan lain - apakah ini terkait langsung dengan keterhubungan real?

Shachaf

Saya menambahkan penjelasan tentang fakta bahwa teorema Rice sebenarnya adalah bentuk teorema keterhubungan.

Andrej Bauer

Misalkan dan tentukan jika tidak berhenti di dalam langkah dan jika tidak. Jika T tidak berhenti maka konvergen ke , sebaliknya konvergen ke . Jika dapat dihitung, maka diberikan , seseorang dapat menghasilkan mesin yang menghitung batas . Mengapa ini tidak cukup untuk menunjukkan bahwa tidak dapat dihitung, atau bahkan dapat dipilih (karena tidak menghentikan iff adalah

p (x) = 1, p (x^{'}) = 0

$p(x)=1, p(x')=0$

y_{i} = x

$y_i=x$

T

$T$

i

$i$

y_{i} = x^{'}

$y_i=x'$

y_{i}

$y_i$

x

$x$

x^{'}

$x'$

x, x^{'}

$x,x'$

T

$T$

y_{i}

$y_i$

p

$p$

T

$T$

p

$p$

1

$1$ pada batas). Jelas saya kehilangan sesuatu, karena ada properti nontrivial yang dapat ditentukan.

Ariel

Definisi ok, tetapi Anda juga memerlukan tingkat konvergensi urutan yang dapat dihitung untuk mengklaim bahwa batasnya dapat dihitung. Karena kita tidak bisa menghitung di mana indeks urutan mungkin melompat dari ke (atau kita bisa menghitung di mana langkah akan menghentikan), seperti tingkat komputasi konvergensi tidak dapat memiliki.

T

$T$

y_{i}

$y_i$

i

$i$

y_{i}

$y_i$

x

$x$

x^{'}

$x'$

T

$T$

Andrej Bauer

Tidak. Atau, paling tidak, buktinya tidak sepele, karena Anda dapat memilih di antara (umumnya banyak) cara yang mungkin untuk menghitung yang nyata, dan mungkin dapat memilih satu dengan struktur yang total tergantung pada properti yang dipilih sehingga Anda tidak mengurangi pengujian properti untuk masalah penghentian.

Juga, saya pikir saya perlu pemahaman yang lebih baik tentang apa artinya "nontrivial" yang berarti sifat-sifat angka. Untuk teorema Rice, "nontrivial" pada dasarnya adalah non-sintaksis dan tidak tersirat oleh sintaksis. Namun setiap bilangan real yang dapat dihitung bukan satu program, melainkan kelas ekivalensi yang penuh dengan program.

Boyd Stephen Smith Jr.
sumber

Saya tidak yakin apa yang Anda maksud, di sini. Apakah Anda mencoba membedakan antara bilangan real yang dapat dihitung (mis. , , , dll.) Dan program yang menghitungnya? Tentu, ada banyak sekali program yang menghitung masing-masing yang benar-benar dapat dihitung tetapi ada juga banyak mesin Turing yang menentukan bahasa yang dapat dipilih, dan teorema Rice yang biasa tidak memiliki masalah dengan itu.

2

$2$

22 / 7

$22/7$

π

$\pi$

David Richerby

Apakah representasi yang berbeda dari real yang dihitung sebenarnya memiliki sifat komputabilitas yang berbeda secara signifikan? Katakanlah saya menggunakan salah satu definisi di en.wikipedia.org/wiki/Computable_number , mis. Real yang dapat dihitung diwakili oleh program yang mengambil batasan kesalahan rasional dan menghasilkan perkiraan dalam batasan itu. Maksud saya "sepele" dalam arti yang sama dengan teorema Rice: Sebuah properti yang berlaku untuk semua real yang dapat dihitung atau tidak satupun dari mereka. Memang benar bahwa setiap angka dapat diwakili oleh beberapa program, tetapi itu berlaku juga untuk fungsi parsial.

Shachaf

@Shachaf Itu lebih "sepele" dari yang dibutuhkan oleh Teorema Rice. "Sintaksis" properti juga sepele - misalnya "memiliki setidaknya 4 negara dapat dicapai dari keadaan awal", "memiliki grafik keadaan terhubung", "tidak memiliki transisi yang menulis X ke kaset", dll - dan mereka perlu tidak berlaku untuk setiap mesin.

Boyd Stephen Smith Jr

@ DavidRicherby Ya, saya pikir perbedaan itu perlu. Jika Anda dapat bekerja secara eksklusif dengan representasi total atau produktif, Anda memiliki kekuatan lebih.

Boyd Stephen Smith Jr.

Teorema Rice adalah tentang sifat-sifat fungsi parsial, bukan algoritma yang menghitungnya. Saya juga bertanya tentang properti real yang dapat dihitung, bukan program yang menghitungnya.

Shachaf

Properti yang dapat ditentukan dari real yang dapat dihitung

Jawaban: