Problem z obliczalnością nauczania

22

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.

mcKlane
źródło
10
„Każda funkcja, którą komputer może obliczyć”? Zwykle sięgam po języki programowania, ponieważ uczniowie prawdopodobnie znają jeden. Skorzystałem też z „dowolnego przepisu na obliczenie funkcji” jako intuicyjnej definicji algorytmu.
Michaël Cadilhac
5
Problem można obliczyć, jeśli można go rozwiązać za pomocą skończonego zestawu reguł rządzących ewolucją dyskretnego układu dynamicznego w skończonej liczbie kroków.
Mohammad Al-Turkistany
1
Można również użyć dziesiątego problemu Hilberta, aby wyjaśnić uczniom, dlaczego jest on nierozwiązywalny i że dowód na nierozwiązywalność wymagał, między innymi, sformalizowania pojęcia obliczalności w matematyce.
Mohammad Al-Turkistany
Inne pytanie: Teza Kościoła-Turinga stwierdza, że ​​funkcja może być obliczona przez jakąś maszynę Turinga, i tylko wtedy, gdy może być obliczona przez jakąkolwiek maszynę innego „rozsądnego i ogólnego” modelu obliczeń [Goldreich, 2008]. Czy można sobie wyobrazić niezależne od modelu pojęcie obliczalności?
MS Dousti,

Odpowiedzi:

37

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.

Andrej Bauer
źródło
2
Bardzo podoba mi się ten argument, ponieważ przechodzi on od betonu (iPhone) do streszczenia.
Suresh Venkat
2
Oto interesująca łamigłówka: jakie są twierdzenia smn i utm w Haskell?
Andrej Bauer,
18
„75 lat temu w pobliżu nie było komputerów”. To jest po prostu nieprawda. 75 lat temu było dużo komputerów. Byli to ludzie, głównie kobiety; mieli zaawansowane stopnie matematyczne, kilka podstawowych narzędzi do obliczeń mechanicznych (takich jak dodawanie maszyn i suwaków) oraz mnóstwo papieru. Komputery te były kręgosłupem zarówno Projektu Manhattan, jak i Bletchley Park podczas II wojny światowej (niezależnie od Bomb i Bombe). To środowisko komputerowe, które modelował Turing: ludzie ołówkiem i papierem.
Jeffε
10
@Jeffe: Daj spokój, wiesz o co mi chodziło.
Andrej Bauer,
8
@JeffE: możemy przetestować twoją hipotezę. Idź do swoich kolegów i poproś, aby narysowali obraz „komputera w krótkiej spódniczce”. Proszę podać, ile osób narysowało człowieka.
Andrej Bauer,
12

„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.

Peter Boothe
źródło
3
Nitpicking: twierdzenie Abla – Ruffiniego stwierdza, że ​​nie ma ogólnego rozwiązania algebraicznego - to znaczy rozwiązania w rodnikach - do równań wielomianowych stopnia piątego lub wyższego. Istnieją jednak metody, takie jak rodnik Bringa, w celu uzyskania zamkniętych rozwiązań równań kwintycznych.
MS Dousti
Twoje nitpicking jest właściwie od razu. Omawiając obliczalność, chcesz porozmawiać o „dozwolonych operacjach”, a rozwiązania wielomianów są jedną z tych rzeczy, które stają się bardziej złożone, im bliżej na to spojrzysz. Ale na wstępie uważam, że słowa „skuteczna procedura” i wzmianka o formule kwadratowej stanowią świetny punkt wyjścia. Nie są całkowicie poprawne, ale intuicja jest całkiem trafna, IMO.
Peter Boothe
8

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”.

Dave Clarke
źródło
6

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.

Kevin Wortman
źródło
0

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.

kumar z winogron
źródło
Pytanie dotyczy nauczania obliczalności. Byłoby dobrze, gdybyś ograniczył swoją odpowiedź do materiałów odpowiadających na to pytanie. Należy pamiętać, że PO uczy studentów, więc osobiste opinie (takie jak trzy ostatnie wypowiedzi) mogą nie być objęte zakresem.
Vijay D