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?

— Jyotirmoy Pramanik
źródło

Jeśli język wszystkich możliwych słów jest niepoliczalny (co wymaga niepoliczalnego alfabetu), natychmiast zapewnia przykład (trywialnie) rozstrzygającego języka Turinga, którego nie można policzyć. Jeśli nie jest (tzn. Jest policzalny), to podjęzyki też nie są niepoliczalne.

— Marc van Leeuwen

Odpowiedzi:

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.

— Yuval Filmus
źródło

A co z zestawem wszystkich języków o skończonej liczbie ciągów znaków w nieskończenie licznym alfabecie? Czy to jest policzalne czy niepoliczalne? Nie mogłem też wymyślić dowodu na to, że „język ponad nieskończenie nieskończonym alfabetem jest policzalny”.

— anir

Twój zestaw jest również policzalny.

— Yuval Filmus,

Dowodzi to, że „zestaw języków nad skończonym alfabetem jest policzalny”. Wydaje mi się, że możemy udowodnić, że „zestaw języków zawierający licznie nieskończone ciągi znaków nad skończonym alfabetem jest policzalny”, stosując to samo podejście dowodowe ze względu na skończony alfabet. Ale nie jestem w stanie wyobrazić sobie, w jaki sposób można dostosować to podejście do nieskończenie licznego alfabetu.

— anir

Nie możesz tego udowodnić, ponieważ jest to fałsz. Liczba nieskończonych sekwencji binarnych jest już niepoliczalna.

— Yuval Filmus,

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$

— Shreesh
źródło

Dlaczego alfabet miałby być policzalny?

— lewo wokół

Każdy badany model ma skończony alfabet. Jeśli alfabet również staje się nieskończony (policzalny lub niepoliczalny), trudno jest mieć rozsądny model.

— Shreesh

@Shreesh Cóż, jeśli alfabet jest niepoliczalny, naiwne mapowanie FSM (z niepoliczalnymi przejściami między skończoną liczbą stanów) może być dość potężne?

— Jak

To prawda, że są to rozszerzenia, które mogą mieć klasy językowe, które mogą być nadklasą języków RE lub języków rekurencyjnych. Ale nie są dobrze badane, jeśli w ogóle są badane. Największym problemem jest, moim zdaniem, sposób przedstawienia skończonej reprezentacji maszyny. Następnie musisz zapisać symbol w komórce taśmy. Nawet skromna komórka może potrzebować nieskończonej pamięci do przechowywania opisu zapisywanego symbolu taśmy.

— Shreesh

To świetne wytłumaczenie. Dodałbym, że nawet jeśli stosowane jest zwykłe kryterium akceptacji / odrzucenia, można powiedzieć, że nadal istnieją pewne języki, na które maszyna Turinga mogłaby zdecydować i które technicznie miałyby niezliczoną liczbę ciągów, ale tylko dlatego, że znaczna większość znaków to „ bezużyteczne ”dla języka.

— Owen

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:

$k\in \mathbb{N}$ $k$ $k$ $3$ $6$
$0$ $10$
$L_i$ $L = \cup_i L_i$ $L$ $L$ $L$
Język jest rozstrzygalny, zarówno język, jak i jego uzupełnienie są częściowo rozstrzygalne.
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 .

— Kaveh
źródło

„ W rezultacie wszystkie języki są skończone ” - masz na myśli policzalność?

— Anton Trunov

Myślę, że tak, panie Trunov.

— Jyotirmoy Pramanik

To fajny post, ale nie rozumiem, co ma wspólnego z konkretnym pytaniem tutaj zadanym. Może chciałeś stworzyć parę pytanie-odpowiedź?

— Raphael