Na studiach na zadanie dostałem udowodnienie obliczalności funkcji za pomocą maszyny Turinga i schematu rekurencji. Nie wdając się w szczegóły jestem przekonany, że raczej nie mam żadnych podstaw aby być w stanie to zrobić (można powiedzieć, że nie było tego ani na wykładach ani na ćwiczeniach, przedmiot Matematyka Dyskretna). Czy w związku z tym, ktoś jest w stanie doradzić mi jak się za to zabrać? Każda pomoc jest w cenie (książki, artykuły, notatki, wytłumaczenie, cokolwiek). ;) Funkcja do udowodnienia: x^2 * sgy + z.
0
0
za pomocą maszyny Turinga - napisanie programu na maszynę Turinga powinno załatwić sprawę.
i schematu rekurencji - musisz złożyć funkcję z prostszych. Tu masz przykłady: http://studia.elka.pw.edu.pl/pub/19L/103A-INxxx-ISP-LTM/teoria/ltm_wyklad_14.pdf
Albo zrobić jedno z powyższych i powołać się na jakieś twierdzenie, które mówi, że jedno istnieje, gdy drugie istniej (już dobrze tego nie pamiętam, ale obstawiam, że takie twierdzenie się znajdzie).
Sprawdź, czy nie ma skryptu do tego :P