Pytania oznaczone «computability»

17
Czy interakcja ma większą moc niż algorytmy?

Słyszałem motto oddziaływanie jest silniejsze niż algorytmów z Peterem Wegner . Podstawą tego pomysłu jest to, że (klasyczna) Maszyna Turinga nie jest w stanie poradzić sobie z interakcją, to znaczy komunikacją (wejście / wyjście) ze światem zewnętrznym / środowiskiem. Jak to może być tak? Jak...

15
Dlaczego kompletność Turinga jest słuszna?

Korzystam z komputera cyfrowego, aby napisać tę wiadomość. Taka maszyna ma właściwość, która, jeśli się nad tym zastanowić, jest naprawdę niezwykła: jest to jedna maszyna, która przy odpowiednim zaprogramowaniu może wykonać dowolne możliwe obliczenia . Oczywiście kalkulatory tego rodzaju wracają...

15
Turinga pełna i obliczeniowa moc

W wykładzie profesor wspomniał, że współczesne komputery nie mają tak dużej mocy obliczeniowej jak maszyna Turinga, ponieważ nie mają nieskończonej pamięci, a ponieważ żaden komputer nie ma nieskończonej pamięci, maszyna Turinga jest zatem nieosiągalna i po prostu reprezentuje górną granicę...

14
Ł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...

14
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 TM,...