Czy istnieje jakiś niezliczony język Turinga?

Istnieje wiele (i mam na myśli wiele) języków, które można policzyć w Turingu. Czy jakiś niezliczony język może być rozstrzygalny przez Turinga?

Każdy język na skończonym (lub nawet policzalnym) alfabecie jest policzalny. Zakładając, że alfabet maszyny Turinga jest skończony, każdy język, który może zaakceptować, jest policzalny.

Możemy mieć niepoliczalne języki tylko wtedy, gdy pozwolimy na słowa o nieskończonej długości, patrz na przykład język regularny Omega . Te języki są nazywane languages. Innym przykładem będzie język podzbioru liczb rzeczywistych, który zawiera, powiedzmy, dziesiętne rozwinięcia wszystkich liczb rzeczywistych.$\omega$

Istnieje kilka modeli, w których modyfikuje się maszyny Turinga, aby akceptowały języki . Niektóre z tych modeli używają warunku Buchi do akceptacji. Ponieważ nie można zobaczyć całości danych wejściowych w skończonym czasie, mówimy, że dane wejściowe są akceptowane, jeśli Maszyna Turinga wejdzie w stan akceptacji nieskończenie wiele razy. Jeśli możemy to udowodnić, analizując dane wejściowe (a nie uruchamiając je), mówimy, że dane wejściowe są akceptowane.$\omega$

Klasyczna obliczalność omawia funkcje nad skończonymi łańcuchami ze skończonego alfabetu. W rezultacie policzalne są wszystkie języki rozstrzygalne lub nierozstrzygalne.

Aby uwzględnić niezliczone języki, musimy spojrzeć na łańcuchy nieskończone zamiast łańcuchów skończonych. (AFAIK, posiadanie nieskończonego alfabetu nie jest zbyt interesujące i nie odpowiada samemu realistycznemu modelowi obliczeń.)

Istnieją modele obliczeń, w których możemy radzić sobie z nieskończonymi ciągami, które pozwalają nam reprezentować obiekty z niezliczonych domen, takie jak liczby rzeczywiste. Są one często przedstawiane jako obliczenia wyższego typu. Jednym z modeli wykorzystujących maszyny Turinga jest model TTE. W tym modelu dane wejściowe mogą być nieskończonymi ciągami, a maszyny mogą uzyskać dostęp do dowolnego elementu w ciągu, który chce. Maszyna nie musi się kończyć, ale istnieją warunki, aby upewnić się, że dane wyjściowe maszyny są zbieżne.

$\Sigma^\omega$$\Sigma$$\Sigma = \{0,1\}$$\Sigma^\mathbb{N} = 2^\mathbb{N}$$2^{2^\mathbb{N}}$

$M$$L \in \Sigma^*$$N$$x\in \Sigma^\omega$$M$$x$$N$$x$$L$

Krótko mówiąc, obliczenie maszyn Turinga, które zawsze się zatrzymują, jest określone przez obliczenie maszyny Turinga na skończonych łańcuchach.

Podam przykład rozstrzygających i nierozstrzygalnych języków nieskończonych ciągów:

1. $k\in \mathbb{N}$$k$$k$$3$$6$

2. $0$$10$

3. $L_i$$L = \cup_i L_i$$L$$L$$L$

4. Język jest rozstrzygalny, zarówno język, jak i jego uzupełnienie są częściowo rozstrzygalne.

5. Język zawierający nieskończone ciągi zerowe nie jest rozstrzygalny. Może to wyglądać dziwnie, ale spójrz na to w ten sposób: kiedy czytasz ciąg znaków, kiedy można go zatrzymać i powiedzieć, że dane wejściowe składają się ze wszystkich zer? Jeśli przestaniesz po przeczytaniu$k$$k$

$x \mapsto \lg x$$x$$\lg x$ do nas.

$f$$\{0,1\}$$f^{-1}(1)$". Na stronie znajduje się również wiele innych odniesień do Obliczalności i złożoności w Analysis Network .