Ha senso dire se un sistema operativo è completo di Turing

Probabilmente no.

I sistemi operativi espongono un'API che fornisce servizi. Nonostante l'apparente complessità, la stragrande maggioranza delle chiamate di servizio in un'API del sistema operativo sono proprio questo: chiamate di servizio e nient'altro. I sistemi operativi in genere non forniscono servizi di looping o altri meccanismi di una macchina completa di Turing; i linguaggi di programmazione forniscono tali meccanismi (cioè i linguaggi di programmazione che chiamano l'API OS).

Se una chiamata al SO fornisce un servizio di looping (ad es. attraversando tutti i file in una cartella) o qualche altra operazione che caratterizza un meccanismo di completamento di Turing, lo fa per volere del codice scritto da qualche programmatore in un linguaggio di programmazione completo di Turing.

In genere direi "no" con un avvertimento.

La difficoltà principale è che la frase "sistema operativo" è molto ampia - un "sistema operativo" potrebbe essere un microkernel autonomo senza servizi collegati, o un sistema operativo potrebbe essere un ambiente grafico multiutente con un centinaio di sottosistemi, o ovunque nel mezzo.

Quando decomponi un sistema operativo moderno, potresti scoprire che include componenti o servizi completi di Turing. Ad esempio, il sistema operativo "Debian" include "bash" come parte centrale del sistema - senza bash (o qualche workalike), non lo si riconoscerà come lo stesso sistema operativo. Bash, ovviamente, fornisce un linguaggio di programmazione completo di Turing.

Potresti dire che Debian è indirettamente Turing-completo - perché ha un componente completo di Turing. Ma questa è un'attribuzione errata. Se volevi avere una discussione sulla solidità computazionale dell'UX in stile Unix, parleresti con gli autori di bash, non con gli autori di Debian.

Dipende da come viene implementato il sistema operativo e da come rispondi alla domanda su cosa fa parte del sistema operativo e cosa non lo è.

Come altre risposte hanno già commentato, un sistema operativo può fornire un linguaggio di scripting come parte della sua shell. Se questo si può dire per rendere completo il sistema stesso è una questione di semantica: la shell è vista come il sistema operativo. Molti risponderebbero "no" - una shell è solo un'interfaccia utente, il sistema operativo stesso è più basso di quello.

Nella maggior parte dei casi, un sistema operativo è implementato come un livello di astrazione su hardware. L'hardware fornisce l'elaborazione, e sia il software utente che il sistema operativo sono implementati usando questo. In questo caso, è abbastanza chiaro che il sistema operativo stesso non è completo - l'hardware sottostante fornisce quella proprietà.

Ma ci sono una manciata di casi diversi, principalmente nei sistemi di ricerca accademici:

• In alcuni sistemi l'hardware e il sistema operativo sono collegati in modo indissolubile in modo tale che dal punto di vista dell'utente finale non ha realmente senso distinguere l'uno dall'altro. Un esempio potrebbe essere CAP o Flex machine .

• In alcuni sistemi il sistema operativo fornisce un linguaggio di programmazione su cui devono essere scritte tutte le applicazioni utente o una macchina virtuale che devono utilizzare. Gli esempi includono il sistema operativo LISP aka Genera e Microsoft Singularity .

In entrambi i casi, la risposta è probabilmente sì.

I sistemi operativi sono lingue. E i sistemi operativi sono macchine. Quindi, sì, ha effettivamente senso parlare di tutte le stesse cose di cui parliamo per Lingue e Macchine: Potere Computazionale, Espressività, Ortogonalità, Composizionalità, Modularità, ecc.

Il fatto che i sistemi operativi siano lingue sembra così ovvio che non c'è nemmeno una discussione a riguardo a cui ci si possa collegare. I duali ( Languages Are Operating Systems ) sembrano essere discussi in modo più vivido, e c'è una citazione su quella pagina che dice:

The converse, that operating systems are languages is widely known. Where does an OS designer get inspiration from if not from various languages? This is especially true in the case of functional languages. (Damn those bastards, always twenty years ahead of the rest of us.)

(Enfasi mia.)

Una macchina di Turing è uno di un particolare insieme di costrutti matematici che accetta una stringa come input e restituisce "true", restituisce "false" o non restituisce mai.

Dire che una macchina di Turing U è una macchina di universale , c'è un modo per prendere qualsiasi macchina M di Turing e qualsiasi stringa di input I e rappresenta ( M , I ) esattamente una stringa S tale che se M restituisce un risultato per I , quindi U restituisce lo stesso risultato per S .

Per dire un linguaggio di programmazione è completo Turing è dire che l'interprete è una macchina di Turing universale. (La combinazione di un compilatore e del computer su cui è in esecuzione il codice compilato può essere definita un "interprete".) Il programma è la stringa di input dell'interprete e il valore di output è qualsiasi cosa scegliamo di osservare sull'output dell'interprete quando il il programma viene eseguito - un determinato carattere stampato sulla console potrebbe significare "true", un codice di stato zero potrebbe significare "true", ecc.

La difficoltà di dire se un sistema operativo è completo di Turing risiede nella difficoltà di definire quale sia il suo input e output. È banalmente Turing completo se si definisce il suo input come combinazione del suo file system (dove può essere archiviato un file eseguibile) e la sua shell (dove un comando può essere inserito per eseguire un file eseguibile). Se è possibile utilizzare la shell direttamente per scrivere su un file (ad esempio echo "this is my program" > program.txt ), eseguire un compilatore su quel file e quindi eseguire l'output del compilatore, quindi la shell stessa è banalmente una macchina di Turing. In alcuni sistemi operativi, la shell è non banale una macchina di Turing universale, anche senza toccare il file system, grazie a un linguaggio di scripting della shell.

Per ogni dato sistema operativo generale, ci sono probabilmente molti altri modi creativi per definire il suo "input" e "output" in modo tale che sia una macchina di Turing universale. Questo potrebbe essere davvero una brutta cosa, perché ciò significherebbe che esiste un modo creativo per far sì che il sistema operativo entri in un ciclo infinito e non lo risponda.