Pytania otagowane jako computability

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

2
Co to są bardzo krótkie programy o nieznanym statusie zatrzymania?
Ten 579-bitowy program w Binary Lambda Calculus ma nieznany status zatrzymania: 01001001000100010001000101100111101111001110010101000001110011101000000111001110 10010000011100111010000001110011101000000111001110100000000111000011100111110100 00101011000000000010111011100101011111000000111001011111101101011010000000100000 10000001011100000000001110010101010101010111100000011100101010110000000001110000 00000111100000000011110000000001100001010101100000001110000000110000000100000001 00000000010010111110111100000010101111110000001100000011100111110000101101101110 00110000101100010111001011111011110000001110010111111000011110011110011110101000 0010110101000011010 Oznacza to, że nie wiadomo, czy ten program się zakończy, czy nie. Aby to ustalić, musisz rozwiązać hipotezę Collatza - lub przynajmniej dla wszystkich liczb do 2 ^ 256. W tym …
2
NP-Trudne problemy, których nie ma w NP, ale są rozstrzygalne
Zastanawiam się, czy istnieje dobry przykład łatwego do zrozumienia problemu NP-Hard, który nie jest NP-Complete i nie jest nierozstrzygalny? Na przykład problem zatrzymania jest NP-trudny, a nie NP-kompletny, ale jest nierozstrzygalny. Uważam, że oznacza to, że problem można zweryfikować, ale nie w czasie wielomianowym. (Proszę poprawić to oświadczenie, jeśli tak …
1
Twierdzenie Rice'a o właściwościach nie semantycznych
Twierdzenie Rice'a mówi nam, że jedynymi właściwościami semantycznymi Maszyn Turinga (tj. Właściwościami obliczonymi przez maszynę), o których możemy decydować, są dwie trywialne właściwości (tj. Zawsze prawdziwe i zawsze fałszywe). Ale istnieją inne właściwości Maszyn Turinga, których nie można rozstrzygać. Na przykład właściwość, że istnieje stan nieosiągalny w danej maszynie Turinga, …
7
Czy istnieje bardziej intuicyjny dowód nierozstrzygalności problemu zatrzymania niż przekątna?
Rozumiem dowód nierozstrzygalności problemu zatrzymania (podany na przykład w podręczniku Papadimitriou), oparty na przekątnej. Chociaż dowód jest przekonujący (rozumiem każdy jego krok), nie jest dla mnie intuicyjny w tym sensie, że nie widzę, jak ktoś by go wyprowadził, zaczynając od samego problemu. W książce dowód wygląda następująco: „załóżmy, że MHMHM_H …
2
Teza Churcha-Turinga i moc obliczeniowa sieci neuronowych
Teza Church-Turinga stwierdza, że ​​wszystko, co można fizycznie obliczyć, można obliczyć na maszynie Turinga. Artykuł „Obliczenia analogowe przez sieci neuronowe” (Siegelmannn i Sontag, Theoretical Computer Science , 131: 331–360, 1994; PDF ) twierdzi, że sieć neuronowa o określonej formie (ustawienia są przedstawione w artykule) jest silniejsza. Autorzy twierdzą, że w …
4
Co miał na myśli Turing, mówiąc, że „maszyny nie mogą wywoływać niespodzianek” wynika z błędu?
Natknąłem poniżej rachunku przez Alana M. Turinga tutaj : „Pogląd, że maszyny nie mogą wywoływać niespodzianek, jest, jak sądzę, spowodowany błędem, któremu szczególnie podoba się filozofów i matematyków. Jest to założenie, że jak tylko fakt zostanie przedstawiony umysłowi, wszystkie konsekwencje tego faktu stają się widoczne umysł jednocześnie z nim. Jest …
2
Dlaczego jest więcej funkcji, które nie są obliczalne niż funkcje obliczalne?
Obecnie czytam książkę o algorytmach i złożoności. W tej chwili czytam o funkcjach obliczalnych i niepoliczalnych, a moja książka stwierdza, że ​​jest o wiele więcej funkcji, które nie są obliczalne niż obliczalne, w rzeczywistości większość jest niepoliczalna. W pewnym sensie intuicyjnie mogę to zaakceptować, ale książka nie daje formalnego dowodu …
2
Dlaczego sumy funkcji nie są policzalne?
Dowiedzieliśmy się o koncepcji wyliczenia funkcji. W praktyce odpowiadają one językom programowania. W pewnej uwadze profesor wspomniał, że klasa wszystkich całkowitych funkcji (tj. Funkcji, które zawsze kończą się dla każdego wejścia) nie jest wyliczalna. Oznaczałoby to, że nie możemy opracować języka programowania, który pozwala nam pisać wszystkie funkcje całkowite, ale …
2
Dlaczego typ pustki C nie jest analogiczny do typu pusta / dolna?
Wikipedia, jak również inne źródła, które znalazłem, wskazują voidtyp C jako typ jednostki, a nie typ pusty. Uważam to za mylące, ponieważ wydaje mi się, że voidlepiej pasuje do definicji typu pustego / dolnego. voidO ile wiem, nie zamieszkują żadnych wartości . Funkcja z typem zwracanym void określa, że ​​funkcja …
28 type-theory  c  logic  modal-logic  coq  equality  coinduction  artificial-intelligence  computer-architecture  compilers  asymptotics  formal-languages  asymptotics  landau-notation  asymptotics  turing-machines  optimization  decision-problem  rice-theorem  algorithms  arithmetic  floating-point  automata  finite-automata  data-structures  search-trees  balanced-search-trees  complexity-theory  asymptotics  amortized-analysis  complexity-theory  graphs  np-complete  reductions  np-hard  algorithms  string-metrics  computability  artificial-intelligence  halting-problem  turing-machines  computation-models  graph-theory  terminology  complexity-theory  decision-problem  polynomial-time  algorithms  algorithm-analysis  optimization  runtime-analysis  loops  turing-machines  computation-models  recurrence-relation  master-theorem  complexity-theory  asymptotics  parallel-computing  landau-notation  terminology  optimization  decision-problem  complexity-theory  polynomial-time  counting  coding-theory  permutations  encoding-scheme  error-correcting-codes  machine-learning  natural-language-processing  algorithms  graphs  social-networks  network-analysis  relational-algebra  constraint-satisfaction  polymorphisms  algorithms  graphs  trees 
6
Czy istnieją programy, które potrafią „tłumaczyć” kod źródłowy między dowolnymi dwoma językami?
Czy istnieją programy, które potrafią „tłumaczyć” kod źródłowy między dowolnymi dwoma językami (zakładając, że tłumacz ma dostęp do wymaganych bibliotek)? Jeśli tak, to w jaki sposób działają (zastosowane techniki, wymagana wiedza itp.)? Jak można by je wykonalnie skonstruować? Jeśli nie są, jakie są ograniczenia uniemożliwiające ich rozwój? Czy jest to …
2
Czy są jakieś szczególne problemy, o których wiadomo, że są nierozstrzygalne z powodów innych niż przekątna, samodzielne odniesienie lub redukowalność?
Każdy nierozstrzygnięty problem, który znam, należy do jednej z następujących kategorii: Problemy nierozstrzygalne z powodu diagonalizacji (pośrednie samodzielne odniesienie). Problemy te, podobnie jak problem zatrzymania, są nierozstrzygalne, ponieważ można użyć rzekomego decydenta dla języka do zbudowania bazy TM, której zachowanie prowadzi do sprzeczności. Możesz także wrzucić do tego obozu wiele …
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.