Aiuta con la ricerca di un difetto nell'argomento simulando grandi macchine di tenuto con quelle più piccole

Question

Ho un argomento che, se attraversa, solo per dimostrare che:

.
• Le lingue di programmazione sono più potenti delle macchine di Turing
• La funzione di castoro occupato ( $ BB () $ ) su macchine per la formicoltura è calcolato

Ora, capisco che è molto più probabile che il mio argomento abbia alcuni difetti che non riesco a trovare. Ma è più interessante per me come ho torto, piuttosto che se ho torto.

argomento

Costruisci una macchina di Turing $ M_1 $ come che prende come argomenti (sul nastro) $ n, k $ < / span>, simula tutte le macchine di turing con $ N $ afferma fino a $ k $ di loro, e Quindi si ferma. Questo è facile da scrivere in un linguaggio di programmazione, come dimostrato dal seguente snippet Python:

def M1(n, k):
    all_machines = generate_turing_machines(n)
    is_halted = [0] * len(generate_turing_machines)
    while sum(is_halted) < k:
        for (i, machine) in enumerate(all_machines):
            machine.step()
            if machine.is_halted():
                is_halted[i] = 1

.

Ora, let $ M_1 $ essere il numero di stati richiesti da $ m_1 $ . Risolto $ N $ molto maggiore di $ m_1 $ . Let $ k_1 $ Sii il numero più grande in modo tale che $ m_1 (n, k_1) $ silenzi e $ k_0 $ Sii il numero più piccolo in modo tale che quando $ m_1 (n, k_0) $ halts, $ k_1 $ Le macchine di formazione simulate sono fermate (come tutte le macchine equivalenti si fermeranno sullo stesso passo). Scegli $ K $ con $ k_0 \ leq k \ leq k_1- $ . Ciò significa che $ M_1 (n, k) $ si ferma in circa $ BB (n) $ passaggi.

Costruisci $ m_2 $ che è lo stesso di $ m_1 $ tranne la prima cosa che fa è Scrivi $ N $ e $ k $ al nastro. Let $ M_2 $ Sii il numero di stati richiesti da $ m_2 $ . Quindi $ M_1 + K (N) + K (k) + c= m_2 $ per alcuni piccoli $ c $ (che è probabilmente costante e probabile $ 0 $ ), con $ k (n) $ Essere il Complessità di Kolmogorov di $ N $ in Turing Machine state.

Ora, $ k (n) $ è al massimo $ o (\ log (n)) $ . Ci sono circa $ N ^ N $ macchine con $ N $ stati, quindi $ k $ è circa $ n ^ n $ , e quindi $ k (k) $ è al massimo $ o (\ log (n ^ n))= o (n \ cdot \ log (n)) $ . Ciò significa che $ m_2> n $ . Ma qui abbiamo un problema: se $ k $ è più facile da scrivere sul nastro (in modo che $ k (k) ), quindi $ m_2 $ sarebbe leggermente più piccolo di $ n $ . Ciò significherebbe $ BB (M_2)> BB (n) $ e $ m_2 , a chiara contraddizione.

Nella mia mente, queste sono le possibili risoluzioni:

.
• $ m_1 $ è impossibile da creare come una macchina di Turing, il che significa che Python è più potente che le macchine.
• Esiste un po 'di estensione transfinita per tingere le macchine che non è molto più potente rispetto alle macchine in generale, e $ M_1 $ può essere scritto in questa estensione. In altre parole, $ M_1 $ è il limite di un set di macchine $ m_ {1, n} $ , ciascuno dei quali può gestire qualsiasi classe $ N . Questo probabilmente comporterebbe la funzione occupata del castoro di essere computabile.
• Esiste un ampio set di numeri che non possono essere scritti da una macchina di Turing in molto meno di $ \ log (k)= n $ stati (abbiamo bisogno < Span class="Math-Container"> $ k (k) ). Mi sembra impossibile che nessun candidato per $ (n, k) $ potrebbe essere sufficientemente compresso.

Dov'è l'errore in questa logica?

---

.

Avevo precedentemente detto che $ k (k) \ leq o (n) $ , ma @ 6005 ha sottolineato che era sospetto. Con quella fissa (a $ o (n \ cdot \ log (n)) $ ), sembra ancora molto sorprendente per me che non possiamo ottenere una riduzione da $ k (k) \ circa n \ cdot \ log (n) $ <

/ span> a $ k (k) per qualsiasi valore potenziale di $ (n, k) $ , ma non più inconcepibile.

Answer 1

Il tuo difetto sembra essere qui:

.

Ora, $ k (n) $ è al massimo $ o (\ log (n)) $ . $ k $ è circa $ n ^ n $ , quindi $ K (k) $ è al massimo $ o (n) $ . Che mette $ M_2 $ solo leggermente più grande di $ n $ .

È vero che $ k $ è circa $ n ^ n $ (più precisamente, $ k= n ^ {\ theta (n)} $ o $ k= 2 ^ {\ theta (n \ log n) } $ , e questo può essere mostrato dal delimitazione superiore $ k $ per il numero di macchine di turing e il limite inferiore trovando una famiglia di semplici fermi macchine). Tuttavia, ciò non implica che $ k (k) $ è al massimo $ o (n) $ . Piuttosto, sappiamo solo che $ k (k) $ è al massimo $$ O (\ log (n ^ n))= o (n \ log n). $$

La tua contraddizione si basa sulla raccolta $ k $ in modo che $ k (k) $ è $ o (n) $ (un po 'più piccolo di $ n $ ). Il tuo ragionamento mostra che questo è impossibile.

Ma questo non è troppo sorprendente: la maggior parte dei $ k $ ci aspettiamo di essere circa $ o (n \ log n ) $ e $ k $ è un numero che contiene molte informazioni sulle macchine di turing con $ n $ afferma, quindi non ci aspettiamo di essere in grado di comprimere un tale numero su un numero più piccolo di $ o (n) $ stati stessi. .

PS Mettendo da parte la questione se Python è davvero equivalente alle macchine di Turing (probabilmente nessuno lo sa, poiché non è stato formalmente mostrato), il tuo programma M1 è in realtà chiaramente espresso come a Macchina di tenuto. Da ciò, dovresti essere in grado di vedere che le risoluzioni basate su M1 non sono espresse come una macchina di Turing non sono corrette.