Problem z obliczalnością nauczania

Mam trudności z nauczeniem pojęcia funkcji obliczalnych. Próbowałem rozwinąć pojęcie, dlaczego badacze tacy jak Hilbert / Ackermann / Godel / Turing / Church / ... wymyślili pojęcie „obliczalności”. Uczniowie natychmiast zapytali: „co oznacza obliczalność?” i nie mogę odpowiedzieć, dopóki nie nauczę ich maszyn Turinga, a następnie odpowiem „funkcja jest obliczalna, jeśli maszyna Turinga ją wyliczy”.

Więc,

Czy istnieje opis obliczalności, która nie wymaga uciekania się do maszyn Turinga, rachunku λ lub podobnych modeli obliczeń? Wystarczy nawet intuicyjny opis.

75 lat temu w pobliżu nie było komputerów. Trzeba więc bardzo dokładnie wyjaśnić matematyczną koncepcję komputera.

Dzisiaj każdy wie, czym jest komputer i prawdopodobnie ma go przy sobie przez większość czasu. Można to z powodzeniem wykorzystać w nauczaniu, ponieważ można pominąć raczej przestarzały pomysł maszyny z taśmą. To znaczy, kto używa taśmy? (Wiem, wiem, czujesz się obrażony, a Turing był świetnym człowiekiem i tak dalej, i zgadzam się z tobą).

Po prostu wchodzisz do klasy i pytasz: czy jest coś, czego twoje iPhone'y nie są w stanie obliczyć? To natychmiast prowadzi do pytań o ograniczone zasoby. Następnie mówisz: załóżmy, że twoja maszyna faktycznie ma nieograniczoną pamięć, czy jest coś, czego nie mogła obliczyć? A ty jeszcze bardziej idealizujesz i ograniczasz uwagę do funkcji teoretycznych (ponieważ obecnie nie interesuje Cię Facebook). Będziesz musiał trochę wyjaśnić, jak działają komputery (jak wspomniano w komentarzach, dobrze jest, jeśli uczniowie znają język programowania, ponieważ możesz go używać zamiast opisywać sprzęt), ale potem możesz użyć wszystkich klasycznych argumentów obliczeniowych teoria do uzyskania wyników. Nie ma znaczenia, że ​​mentalnym obrazem twoich uczniów jest iPhone. W rzeczywistości ma to znaczenie:bardziej odpowiednie dla nich, aby wiedzieć, że ich iPhone nie może robić pewnych rzeczy.

„Funkcja jest obliczalna, jeśli istnieje„ skuteczna procedura ”przechodzenia od wejścia do wyjścia.” Wprowadzając ten temat, w przeszłości zwracałem uwagę na to, jak oni (uczniowie) mają skuteczną procedurę rozwiązywania równań kwadratowych, ale nie mają takiej do rozwiązywania równań stopnia 5 lub więcej. Może to prowadzić do dyskusji na temat tego, jak sformalizować „skuteczną procedurę”, ale ta dyskusja jest czymś, co chcesz, aby się wydarzyło, więc myślę, że jest to cecha, a nie błąd.

Być może chodzi o to, że wszystkie te modele miały na celu uchwycenie pojęcia obliczalności. Fakt, że wszystkie są równoważne, oznacza, że ​​pojęcie, które próbują uchwycić, jest solidne. Chociaż więc nie umknie to twojemu dylematowi, ta solidność daje wiarygodność przekonaniu, że „funkcja jest obliczalna, jeśli istnieje maszyna Turinga, która ją oblicza”.

Zaczynam od pytania: „czy jest jakieś pytanie, na które żaden komputer nie byłby w stanie przekonująco odpowiedzieć?” i poprowadź dyskusję do filozoficznych pytań, takich jak „jeśli drzewo spadnie do lasu, czy to wyda dźwięk?” lub „czy jest życie pozagrobowe?” Szybko osiągamy konsensus, że ludzki język może wyrażać pytania typu tak / nie, dotyczące paradoksów lub pojęć, których nie można wyrazić matematycznie, a więc tak, istnieją pytania, których nie można obliczyć.

Następnie pytam retorycznie, czy istnieją pytania, których nie można obliczyć na temat pojęć, które można przedstawić w komputerze, np. Liczby całkowite i wykresy. Mówię, że tak, jednym z przykładów jest słynny problem zatrzymania, polegający na zbadaniu opisu programu i stwierdzeniu, czy ma on nieskończone pętle. Intuicyjnie okazuje się, że nieskończone pętle są jak czarne dziury, a każdy program, który obserwuje nieskończoną pętlę, może zostać uwięziony w samej pętli nieskończonej. Tak więc każda procedura, która rozwiązuje ten problem, może działać wiecznie, więc zgodnie z definicją „algorytmu” żaden algorytm nie może rozwiązać problemu zatrzymania.

Następnie zagłębiam się w dowody na maszynach Turinga.

Cóż, funkcja jest obliczalna, jeśli akceptuje dane wejściowe, które są tworzone lub generowane przez określony wzorzec. Określony wzorzec oznacza, że ​​wszystkie dane wejściowe powinny mieć relację, dane wejściowe mogą być generowane przez to poprzednie lub następne wejście. Jeśli dane wejściowe nie mają tego rodzaju sekwencji, nie ma możliwości opracowania modelu lub funkcji, które mogłyby zaakceptować. Jeszcze jedno chcę powiedzieć, że istnieje podstawowa różnica między maszyną a człowiekiem. Nie można utworzyć maszyny dla niesekwencyjnych danych wejściowych, ale ludzie są. To także duża przerwa w tworzeniu rzeczywistych robotów zachowujących się w ludziach.