Pytania otagowane jako turing-completeness

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, …
1
Czy istnieje logiczna koncepcja „Turing Complete”?
Można wykazać, że dwa modele obliczeniowe są kompletne, jeśli każdy z nich może zakodować uniwersalny symulator dla drugiego. Można wykazać, że dwie logiki są kompletne, jeśli kodowanie reguł wnioskowania (i może aksjomatów, jeśli są obecne) każdego z nich jest twierdzeniem drugiej. W obliczeniach doprowadziło to do naturalnego pomysłu kompletności Turinga …
1
W jaki sposób uniwersalna maszyna Turinga może symulować „większe”?
Próbuję znaleźć odpowiedzi na dwa pytania dotyczące uniwersalnej maszyny Turinga. Jak uniwersalna maszyna Turinga może symulować maszynę Turinga, jeśli symulowana ma większą liczbę stanów? Jak uniwersalna maszyna Turinga może symulować maszynę Turinga, jeśli symulowana ma większą liczbę znaków alfabetu? Czy ktoś może mi pomóc z tymi pytaniami?
2
Jasny, kompletny, dowód na to, że język jest konkurencyjny w Turingu?
Widziałem strony internetowe, które rzekomo „dowodzą”, że HTML5 + CSS jest Turing Complete. Widziałem strony internetowe, które rzekomo „dowodzą”, że SQL jest Turing Complete. Widziałem kilka stron internetowych, które rzekomo „wyjaśniają”, co to znaczy być Turing Complete. Wystarczająco! Gdzie mogę znaleźć książkę (napisaną przez eksperta w dziedzinie teorii obliczeń) lub …
2
Czy funkcje logiczne Turinga są kompletne?
Funkcja boolowska jest funkcją .fa: { 0 , 1}n→ { 0 , 1 }f:{0,1}n→{0,1}f:\{0,1\}^n\rightarrow\{0,1\} Podstawa logiczna jest znana jako Turing complete, ponieważ pozwala na odwrócenie dowolnej sekwencji lub pozostawienie jej bez zmian. To samo można powiedzieć o bramkach .( ∨ , ∧ )(∨,∧)(\vee,\wedge)s ∈ { 0 , 1 }s∈{0,1}s\in\{0,1\}X O …
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.