JBJDM1712
Ekstra forelæsning i Uge 48: Som tidligere annonceret erstattes forelæsningen den 7/12 af en forelæsning torsdag den 2/12 kl 8-10 i lokale U27.
Forelæsningenerne den 30.11.99 og 2/12
Opgaver til 2/12:
Opgaver fra tidligere ugesedler blive taget op i det omfang jeres instruktor finder det rimeligt.
Lærebogen 5.5.1, 5.7.7, 5.7.11, Januar 96 opgave 5, Juni 96 opgave 5.
NB: Det er vigtigt at I husker konklusionerne fra alle opgaver også selvom I måske ikke har nået at gennemgå dem allesammen.
Opgaver til 9/12 Stilles på ugesedlen i næste uge.
Angående Rice's sætning:
Denne sætning er et meget nyttigt redskab til at vise at mange
spørgsmål om Turing maskiner er uafgørlige. Bemærk, at
sætningen beskæftiger sig med egenskaber ved sprog som
accepteres af Turing maskiner, dvs den kan kun anvendes til
spørgsmål af følgende art: Givet koden for en Turing maskine
M, har L(M) egenskaben 
?. Dvs hvis er den
ikke trivielle egenskab ved rekursivt enumerable sprog, så siger
sætningen, at der ikke findes en Turing maskine der kan afgøre
sproget 
.