Pytania otagowane jako computability

Pytania związane z teorią obliczalności, czyli teorią rekurencji

1
Czy istnieje kompletny problem dla klasy rozstrzygających problemów Turinga?
Języki, takie jak są uzupełniane ponownie przy wielu redukcjach. To banalne, aby zobaczyć, że co-RE ma również kompletne problemy. S. Schmitz [1] rozważa niektóre klasy pomiędzy ELEM a REC . Stanowią one kompletne problemy dla tych klas w ramach specjalnie spreparowanych redukcji.HALTTMHALTTM\text{HALT}_{TM}RE-completeRE-complete\textsf{RE-complete}co-REco-RE\text{co-RE}ELEMELEM\text{ELEM}RECREC\text{REC} Czy istnieją całkowite problemy dla (aka REC ) …
1
W przypadku maszyny Turinga , w jaki sposób zestaw maszyn które są „krótsze” niż i które akceptują ten sam język, jest rozstrzygalny?
Zastanawiam się, jak to się stało, że język jest w następujący .RR\mathrm R L.M.1= { ⟨M2)⟩∣∣M.2) jest TM, a L ( M1) = L ( M2)) , A | ⟨ M1⟩ | > | ⟨ M2)⟩ | }L.M.1={⟨M.2)⟩|M.2) jest TM, i L.(M.1)=L.(M.2)), i |⟨M.1⟩|>|⟨M.2)⟩|}L_{M_1}=\Bigl\{\langle M_2\rangle \;\Big|\;\; M_2 \text{ is a …
2
Czy jest rozstrzygalne, czy TM osiągnie jakąś pozycję na taśmie?
Mam te pytania ze starego egzaminu, który próbuję rozwiązać. Dla każdego problemu wejście jest kodowanie pewnej maszyny Turingowi .MMM Dla liczby całkowitej i następujących trzech problemów:c>1c>1c>1 Czy to prawda, że ​​dla każdego wejścia , M nie przechodzi przez pozycję podczas pracy na ?xxx|x|+c|x|+c|x|+cxxx Czy to prawda, że ​​dla każdego wejścia …
1
Łatwe do stwierdzenia otwarte problemy w teorii obliczalności
Szukałem interesujących i łatwych do stwierdzenia otwartych problemów w zakresie obliczalności (zrozumiałych dla studentów pierwszego roku z zakresu obliczeń), aby podać przykłady otwartych problemów (i oczywiście chcę, aby uczniowie byli w stanie zrozumieć problem bez potrzeby zbyt dużej ilości nowych definicje, a także być dla nich interesujące). Znalazłem tę listę, …
3
nierozstrzygalny problem i jego negacja jest nierozstrzygalna
Wiele „znanych” nierozstrzygalnych problemów jest jednak co najmniej w połowie nierozstrzygalnych, a ich dopełnienie jest nierozstrzygalne. Jednym z przykładów może być przede wszystkim problem zatrzymania i jego uzupełnienie. Czy ktoś może jednak podać przykład, w którym zarówno problem, jak i jego uzupełnienie są nierozstrzygalne i nierozstrzygalne? Myślałem o języku diagonalizacji …
3
Obliczanie funkcji zajętego bobra
Funkcja maksymalnych przesunięć bobra zajętego, , ma znane wartości dla n ≤ 4 . Czy istnieje jakiś podstawowy, strukturalny powód, dla którego jest nie do pomyślenia, abyśmy kiedykolwiek znaleźli S ( n ) dla n > 4 ? Czym tak różni się n = 4 niż n = 5 ? …
3
P, NP i specjalistyczne maszyny Turinga
Jestem w pewnym sensie nowy, ale bardzo zainteresowany dziedziną obliczeń i teorii złożoności, i chcę wyjaśnić moje rozumienie, w jaki sposób klasyfikować problemy i jak silnie problemy odnoszą się do maszyny używanej do ich rozwiązywania. Moje zrozumienie Standardowa maszyna Turinga - maszyna Turinga, która ma skończony alfabet, skończoną liczbę stanów …
2
Czy funkcje nieobliczalne stają się asymptotycznie większe?
Czytam o zajętych liczbach bobrów io tym, jak rosną one asymptotycznie większe niż jakakolwiek obliczalna funkcja. Dlaczego tak jest? Czy to z powodu niemożności obliczenia funkcji zajętego bobra? Jeśli tak, to czy wszystkie funkcje niepoliczalne stają się asymptotycznie większe niż funkcje obliczalne? Edytować: Świetne odpowiedzi poniżej, ale chciałbym wyjaśnić prostszym …
3
Czy każdy algorytm samodmodyfikujący może być modelowany za pomocą algorytmu niemodyfikującego?
Jeśli mamy dowolny dowolny program komputerowy, który może modyfikować jego instrukcje, czy można symulować ten program za pomocą programu, który nie może modyfikować jego instrukcji? Edytować: Jestem nowy w stosie wymiany, więc nie jestem pewien, czy mogę zadawać NOWE pytanie tutaj, ale oto: Ok, więc dowód, że jest to możliwe, …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.