[an error occurred while processing this directive] [an error occurred while processing this directive][an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] (none) [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive][an error occurred while processing this directive] [an error occurred while processing this directive][an error occurred while processing this directive] [an error occurred while processing this directive][an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] (none) [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive][an error occurred while processing this directive]
 
[an error occurred while processing this directive] [an error occurred while processing this directive]
Skåne Sjælland Linux User Group - http://www.sslug.dk Home   Subscribe   Mail Archive   Forum   Calendar   Search
MhonArc Date: [Date Prev] [Date Index] [Date Next]   Thread: [Date Prev] [Thread Index] [Date Next]   MhonArc
 

Re: [MISC] Programmer som formel (Unifolk: LÆS!)



Ole Tange <sslug@sslug> writes:

> Jeg mindes også at man havde et mere matematisk sprog som basalt set også
> kunne beskrives med en Turingmaskine. Jeg mener det var noget med
> lambdakalkyle.

Lad mig starte med at slå fast at alle nedenstående formalismer er
``matematiske sprog''; på den måde afviger de ikke fra hinanden.

Lambdakalkylen er i virkeligheden et meget lille programmeringssprog
med variable, funktioner og funktionsanvendelse. I dette lille sprog
kan man skrive endog mange programmer (hvis man er villig til at
indkode heltal og den slags som termer i sproget). Faktisk er det
sådan at et vilkårligt program til en Turingmaskine kan efterabes af
et lambdakalkyle program. Det svarer så også på dit spørgsmål:

> Har jeg ret i, at et hvert program til en Turingmaskine kan omformuleres
> til en matematisk (evt. rekursiv) formel?

fordi der generelt set er mange programmeringssprogsformalismer der
alle er lige stærke: de kan alle efterabe hinanden. Det drejer sig
f.eks. om ovenstående lambdakalkyle, Turingmaskiner, rekursive
funktioner (som teknisk set er noget andet end lambdakalkylen), m.m.

> Hvis ja: Er der nogen, der har et link til en lidt nærmere beskrivelse af
> fænomenet? 

Sådant noget kan man finde beskrevet i snart sagt enhver bog om
beregnelighed. (Jeg kan da reklamere for vores egen Neil Jones:
Computability and Complexity --- From a Programming Perspective.)

> Findes der en maskinel implementation af sådanoget?

Jeg ved ikke helt hvad du tænker på når du siger ``maskinel
implementation''. I bund og grund er det at ``efterabe'' en maskinel
implementation. Når man siger at lambdakalkyle er lige så stærk som
Turingmaskinen, er det fordi man kan skrive et program, en fortolker,
i lambdakalkylen der afvikler et vilkårligt Turingprogram, og
omvendt. Dette er i høj grad en maskinel implementation.

Jeg forstår ikke helt hvad relationen til software-patenter er ...

Mvh
--Henning Niss

P.S. Hvis man er til visuelle værktøjer og den slags djævelskab, kan
man finde Visual Turing på http://www.cheran.ro/vturing/.

P.P.S. Inden nogle begynder at falde over mig: Jeg snakker om utypede
lambdakalkyler.


 
Home   Subscribe   Mail Archive   Index   Calendar   Search

 
 
Questions about the web-pages to <www_admin>. Last modified 2005-08-10, 20:11 CEST [an error occurred while processing this directive]
This page is maintained by [an error occurred while processing this directive]MHonArc [an error occurred while processing this directive] # [an error occurred while processing this directive] *