Pytania otagowane jako computation-models

Definicja zbioru dopuszczalnych operacji używanych do obliczeń i odpowiadających im kosztów. Niektóre przykłady modeli obejmują maszyny Turinga, funkcje rekurencyjne, rachunek lambda i systemy produkcyjne.

6
Dlaczego maszyna Turinga jest popularnym modelem obliczeniowym?
Jestem studentem CS. Rozumiem, jak Turing wymyślił swoją abstrakcyjną maszynę (modelującą osobę wykonującą obliczenia), ale wydaje mi się to niewygodną, ​​nieelegacyjną abstrakcją. Dlaczego uważamy „taśmę” i maszynę piszącą symbole, zmieniającą stan, przesuwającą taśmę tam iz powrotem? Jakie jest podstawowe znaczenie? DFA jest elegancki - wydaje się, że dokładnie przechwytuje to, …
3
Jak modeluje się złożoność algorytmu dla języków funkcjonalnych?
Złożoność algorytmu została zaprojektowana w taki sposób, aby była niezależna od szczegółów niższego poziomu, ale opiera się na modelu imperatywnym, np. Dostęp do tablicy i modyfikowanie węzła w drzewie zajmuje O (1). Nie dotyczy to wyłącznie języków funkcjonalnych. Dostęp do listy Haskell zajmuje liniowy czas. Modyfikowanie węzła w drzewie wymaga …
2
Kwantowy rachunek lambda
Klasycznie istnieją 3 popularne sposoby myślenia o obliczeniach: maszyna Turinga, obwody i rachunek lambda (używam tego jako haczyka dla większości widoków funkcjonalnych). Wszystkie 3 były owocnymi sposobami myślenia o różnych typach problemów, a różne dziedziny stosują różne formuły z tego powodu. Kiedy jednak pracuję z obliczeniami kwantowymi, zawsze myślę tylko …
7
Różnice i związki między algorytmami losowymi i niedeterministycznymi?
Jakie różnice i zależności występują między algorytmami losowymi a algorytmami niedeterministycznymi? Z Wikipedii Randomizowane algorytm jest algorytmem, w którym stosuje się stopniem losowości jako część logiki. Algorytm zwykle wykorzystuje jednolicie losowe bity jako pomocnicze dane wejściowe do kierowania jego zachowaniem, w nadziei na osiągnięcie dobrej wydajności w „przeciętnym przypadku” względem …
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 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 istnieje fizyczna analogia do maszyny Turinga?
Ostatnio w mojej klasie CS zapoznałem się z Maszyną Turinga. Po zajęciach spędziłem ponad 2 godziny, próbując dowiedzieć się, jaki jest związek między taśmą a maszyną. Byłem całkowicie nieświadomy istnienia taśm komputerowych lub tego, jak taśmy i maszyny współdziałały do ​​dziś. Nadal nie rozumiem, dlaczego maszyna odczytuje taśmy, ale skaner …
8
Język programowania, w którym każde wyrażenie ma sens
Zgodnie z zaleceniem przesyłam ponownie z Przepełnienia stosu . Ostatnio zastanawiałem się nad następującym problemem. Rozważ kod standardowego „Hello world!” program: main() { printf("Hello World"); } Teraz prawie każda zmiana w tym kodzie sprawi, że będzie on całkowicie bezużyteczny, w rzeczywistości prawie każda zmiana uniemożliwi kompilację kodu. Na przykład: main(5 …
5
Czy problem zatrzymania można „rozwiązać”, przechodząc do opisu obliczeń wyższego poziomu?
Niedawno usłyszałem ciekawą analogię, która stwierdza, że ​​dowód Turinga na nierozstrzygalność problemu zatrzymania jest bardzo podobny do paradoksu fryzjerskiego Russella. Zastanawiałem się więc: matematycy w końcu zdołali ujednolicić teorię zbiorów, przechodząc od naiwnego sformułowania pola przez Cantora do bardziej złożonego systemu aksjomatów (teoria zbiorów ZFC), dokonując po drodze istotnych wyłączeń …
1
Maszyny dla języków bezkontekstowych, które nie zyskują dodatkowej mocy z niedeterminizmu
Rozważając modele maszynowe obliczeń, hierarchię Chomsky'ego zazwyczaj charakteryzuje (w kolejności), automat skończony, automat push-down, automat liniowo związany i maszyny Turinga. W przypadku pierwszego i ostatniego poziomu 1 (języki zwykłe i języki z wyliczaniem rekurencyjnym) nie ma różnicy w sile modelu, czy rozważamy maszyny deterministyczne czy niedeterministyczne, tj. DFA są równoważne …
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.