Bisakah kita tidak menampilkan kompleksitas Kolmogorov?

Mari kita perbaiki pengkodean Turing-mesin yang bebas awalan dan universal Turing-machine $U$ yang pada input $(T,x)$ (dikodekan sebagai kode bebas-awalan dari $T$ diikuti oleh $x$ ) menghasilkan keluaran apa pun $T$ pada input $x$ (mungkin keduanya berjalan selamanya). Tentukan kompleksitas Kolmogorov dari $x$ , $K(x)$ , sebagai panjang dari program terpendek $p$ sehingga $U(p)=x$ .

$T$ $x$ $T(x)\le |x|$ $x$ $T(x)\ne K(x)$ $\liminf_{|x|\rightarrow \infty} T(x)=\infty$

Syaratnya perlu, karena

(a) jika, maka akan mudah untuk menghasilkan angka yang secara sepele berbeda dari karena lebih besar dari , $T(x)\not \le |x|$ $K(x)$ $|x|+c_U$

(b) jika $\liminf_{|x|\rightarrow \infty} T(x)<C$ diizinkan, maka kita dapat menampilkan $0$ (atau konstanta lainnya) untuk hampir semua angka, dengan "untungnya" menebak paling banyak (Banyak angka) yang mengevaluasi ke $0$ (ke beberapa konstanta lainnya) dan menghasilkan sesuatu yang lain. Kami bahkan dapat menjamin $\limsup_{|x|\rightarrow \infty} T(x)=\infty$ dengan mengeluarkan sesuatu seperti $2\log n$ untuk $x=2^n$ .

Perhatikan juga bahwa pekerjaan kita akan mudah jika kita tahu bahwa $T(x)$ tidak bersifat surjektif, tetapi sedikit yang diketahui tentang ini, jadi jawabannya mungkin bergantung pada $U$ , meskipun saya ragu itu akan.

Saya tahu bahwa banyak hubungan dipelajari secara umum, tetapi

Adakah yang pernah mengajukan pertanyaan serupa di mana tujuan kami adalah memberikan algoritma yang tidak menghasilkan beberapa parameter?

Motivasi saya adalah masalah ini http://arxiv.org/abs/1302.1109 .

cc.complexity-theory kolmogorov-complexity universal-computation universal-turing-machines domotorp
sumber

Itu tergantung pada penyandian Anda, karena seperti yang disebutkan dalam topik pada surjectivity Anda tautkan, bisa jadi ini merupakan kasus bahwa hanya program panjang genap yang valid. Jadi untuk menjadikan pertanyaan Anda tidak sepele, Anda perlu memiliki lebih banyak hipotesis tentang penyandian.

K

$K$

p

$p$

Denis

Untuk pertanyaan kedua Anda: ya. Dengan diberi bilangan bulat , misalkan menunjukkan mesin T-Fungsi diagonal non-rekursif (atau DNR) adalah fungsi sedemikian rupa sehingga untuk semua bilangan bulat , . (Yaitu, jika berhenti pada , maka , dan jika tidak dapat berubah-ubah.) Ini telah dipelajari sedikit baru-baru ini di computability / computable komunitas keacakan. Google "secara non-rekursif" untuk menemukan makalah tentang ini.

M

$M$

[M]

$[M]$

M

$M$

f : N \to N

$f\colon \mathbb{N} \to \mathbb{N}$

M

$M$

[M] (M) \neq f (M)

$[M](M) \neq f(M)$

[M]

$[M]$

M

$M$

f (M) \neq [M] (M)

$f(M) \neq [M](M)$

f (M)

$f(M)$

Joshua Grochow

@Denis: Saya pikir Anda salah. Menurut definisi saya tentang mesin Turing universal yang diberikan dalam paragraf pertama, semua panjang dapat menjadi program yang valid.

domotorp

Beberapa kali yang lalu saya berpikir (sia-sia) tentang versi yang tampaknya lebih sederhana: (dis) membuktikan bahwa untuk cukup besar , untuk semua .

x_{0}

$x_0$

K (x) \neq | x | / 2

$K(x) \neq |x|/2$

x \geq x_{0}

$x \geq x_0$

Marzio De Biasi

@ Ricky: Tidak apa-apa, saya tidak memiliki batasan pada pengkodean mesin Turing, hanya pada program, yang dapat Anda baca di paragraf pertama.

domotorp

Jawaban:

Pertanyaannya dapat diulang kembali sebagai apakah , dan sebagaimana ditunjukkan Denis dalam komentar ini salah untuk beberapa penyandian. Berikut ini adalah pernyataan yang lebih lemah dan bukti percobaan yang tidak bergantung pada detail pengkodean apa pun, tetapi saya akan menganggap bahasa biner untuk kesederhanaan: $\lim \inf_{\vert x \vert \rightarrow \infty}{\vert T(x) - K(x) \vert} = 0$

Biarkan menjadi fungsi yang dapat memenuhi dan . Kemudian . Secara informal, jika ada target di sekitar kompleksitas Kolmogorov masing-masing string yang tumbuh lebar tanpa batas, tidak ada fungsi yang dapat dikomputasi yang menghindarinya. $T:\{0,1\}^* \rightarrow \mathbb{N}$ $0 \le T(x) \le \vert x \vert$ $\lim \inf_{\vert x \vert \rightarrow \infty}{T(x)} = \infty$ $\lim \inf_{\vert x \vert \rightarrow \infty}{\vert T(x) - K(x) \vert} \lt \infty$

Untuk melihat ini, misalkan menjadi bit acak , yaitu dan . Untuk semua seperti acak itu ada. Juga mencatat bahwa ada jumlah tak terbatas nilai yang , ini mengikuti dari kondisi ditempatkan pada . Sekarang mari menjadi string terkecil sehingga . Jelas ada konstanta sehingga , karena dan $n$ $b$ $0 \le n \lt 2^b$ $K(n) \ge b$ $b$ $n$ $b$ $\vert \{T(x) = b\} \vert \ge 2^b$ $T$ $x$ $n^{\text{th}}$ $T(x) = b$ $c_1$ $K(x) \gt b - c_1$ $K(n) \ge b$ $n$ dapat dihitung dari . Dan ada konstanta sehingga , karena juga dibatasi dari atas dengan hanya konstanta lebih dari , dan dapat dihitung dari . Kemudian , dan kami memiliki jumlah pilihan tak terbatas untuk (yang memiliki perkiraan kardinalitas minimal ), menghasilkan jumlah nilai tak hingga untuk , jadi kita selesai. $x$ $c_2$ $K(x) \lt b + c_2$ $K(n)$ $b$ $x$ $n$ $\vert K(x) - T(x) \vert \lt c_1 + c_2$ $b$ $2^b$ $x$

Implikasinya adalah bahwa untuk beberapa , sering tak terhingga. Jadi bisa dikatakan kita tidak bisa mengeluarkan sesuatu yang bukan kompleksitas Kolmogorov! $c \in \mathbb{Z}$ $T(x) = K(x) + c$

Dan Brumleve
sumber

Bagus, saya pikir ini harus berhasil. Tentu saja, mungkin tidak ada string dengan , jadi mungkin Anda ingin meminta , kan?

f (x) = b

$f(x)=b$

f (x) \geq b

$f(x)\ge b$

domotorp

Itu harus sehingga dapat dihitung dari . Jadi, saya kira kita perlu memilih sehingga atau lebih memetakannya. Agaknya, anggapan-anggapan tersebut seharusnya menyiratkan ada banyak yang tak terhingga banyaknya (walaupun saya tidak begitu melihatnya saat ini). (Sejauh yang saya tahu, asumsi tersebut belum digunakan dengan cara lain.)

f (x) = b

$f(x)=b$

n

$n$

x_{b, n}

$x_{b,n}$

b

$b$

\geq 2^{b + 1}

$\ge2^{b+1}$

b

$b$

Emil Jeřábek mendukung Monica

Ya, memang ini yang dibutuhkan. Tetapi buktinya mudah dengan kontradiksi - jika selalu jika , maka dengan melihat rentang apa pun , kita dapat menyimpulkan bahwa setidaknya string dipetakan ke , dengan demikian tak terhingga banyaknya, yang bertentangan dengan .

< 2^{b}

$<2^b$

b > b_{0}

$b>b_0$

b_{0} < b \leq B

$b_0<b\le B$

B - b_{0}

$B-b_0$

\leq b_{0}

$\le b_0$

lim inf = \infty

$\liminf=\infty$

domotorp

Apa yang dibicarakan Denis tidak berlaku pada cara saya mendefinisikan universalitas pada baris pertama pertanyaan saya. Ucapannya juga sepele, saya tidak tahu mengapa begitu banyak orang yang telah mengangkat komentarnya. Namun sayang, juga jawaban Peter yang salah menerima begitu banyak upvotes, saya kehilangan kepercayaan pada situs ini ...

domotorp

Tidak masalah bagaimana TM disandikan, selama kriteria saya tentang TM universal terpenuhi, jadi komentar Denis tidak benar. Jika itu dinyatakan sebagai komentar tentang model lain, maka itu akan menjadi hal yang berbeda. Bagaimanapun, alih-alih merenungkan ini, mari kita coba untuk melihat apakah kami dapat memperkuat ide Anda ...

domotorp

Saya pikir berikut ini berfungsi. Saya akan menggunakan untuk kompleksitas Kolmogorov $C(x)$

Beri batas waktu (katakanlah, beberapa fungsi eksponensial dari panjang program input), dan panggil hasilnya . Jika suatu program melebihi timebound, memasuki loop tak terbatas. $U$ $t$ $U^t$ $U^t$
Biarkan menjadi program terpendek untuk pada . Perhatikan bahwa dapat dihitung. $C^t(x)$ $x$ $t$ $C^t$
Biarkan mengembalikan , kecuali nilai ini sama dengandi mana case return 0. Kecuali adalah output dari program kosong, di mana case return 1. $T(x)$ $C^t(x) + 1$ $|x|$ $x$
Karena , akan selalu berbeda dari . Logika pada langkah sebelumnya menangani kasus tepi. $C(x) \leq C^t(x)$ $T(x)$ $C(x)$
$U^t$ berfungsi sebagai kode untuk semua string, sehingga memiliki batas infinity inferior.

Peter
sumber

beberapa komentar, teori KC dalam interpretasi alternatif (tetapi setara) menyatakan sebagai berikut: Hampir semua string sudah dalam representasi optimal mereka ( wrt ke model yang diberikan) kecuali banyak string yang dapat didenumerasi yang dapat diubah menjadi representasi optimal (minimum) wrt ke model perhitungan yang diberikan (atau TM). Dalam hal ini hampir setiap program menghasilkan representasi string yang optimal, tetapi ini tidak diketahui (atau dapat dihitung) a-priori

Nikos M.

Mengapa Anda memiliki?

T (x) \leq | x |

$T(x)\le |x|$

domotorp

@domotorp Secara teknis kami memiliki mana adalah panjang dari program cetak terpendek. Tentu saja, konstanta ini juga ada untuk (dan pada kenyataannya, kecuali jika program cetak benar-benar lambat, konstanta yang sama).

T (x) \leq | x | + c

$T(x) \leq |x| + c$

c

$c$

C (x)

$C(x)$

Peter

Tapi inilah yang membuat seluruh pertanyaan menarik! Saya bisa meminta fungsi apa pun alih-alih, misalnya, , satu-satunya tujuan saya adalah menghilangkan solusi yang serupa dengan milik Anda.

| x |

$|x|$

| x | / 2 + 99

$|x|/2+99$

domotorp

@domotrop saya mengerti, jadi Anda ingin memaksa untuk tidak menjadi upperbound ke . Itu lebih menarik ...

T (x)

$T(x)$

C (x)

$C(x)$

Peter