Je commence à lire un livre sur la complexité informatique et les machines de Turing. Voici une citation:
Un algorithme (c'est-à-dire une machine) peut être représenté comme une chaîne de bits une fois que nous avons décidé d'un codage canonique.
Cette affirmation est fournie comme un simple fait, mais je ne peux pas le comprendre.
Par exemple, si j'ai un algorithme qui prend en entrée et calcule ou:
int function (int x){
x = x + 1;
return x**2;
}
Comment cela peut-il être représenté sous forme de chaîne en utilisant l'alphabet ?
algorithms
turing-machines
computability
computation-models
Kenenbek Arzymatov
la source
la source
Réponses:
La réponse la plus naïve et la plus simple à votre question est que le code fourni (et le code machine compilé) sont en fait représentés comme des chaînes syntaxiques de {0,1} *. De plus, puisque vous parlez de machines de turing, les programmes qu'elles exécutent sont une liste linéaire d'opérations / instructions, il n'y a aucune raison pour qu'elles ne puissent pas être représentées en bits / octets.
la source
Vous avez déjà une représentation de cette fonction sous forme de texte. Convertissez chaque caractère en une valeur d'un octet à l'aide du codage ASCII. Le résultat est alors une séquence d'octets, c'est-à-dire une séquence de bits, c'est-à-dire une chaîne sur l'alphabet . C'est un exemple d'encodage.{ 0 , 1 }∗
la source
Je ne peux pas résister ...
(Les points ci-dessus représentent des uns, les zéros blancs).
la source
Votre ordinateur stocke tout comme des séquences de
0et1, y compris la question que vous avez saisi pour demander comment il le fait. Par exemple, chaque lettre et symbole est représenté par 8 bits (je parle de la façon dont les choses étaient, de nos jours c'est 16 bits et plus compliqué). Vous pouvez les voir ici . Eh bien, ils ne montrent pas les bits, mais plutôt les codes hexadécimaux et octaux. Savez-vous comment convertir un nombre en sa représentation numérique?la source
L'hypothèse fondamentale derrière ce concept est la thèse de Church-Turing . Il peut être difficile de voir que n'importe quel algorithme peut être représenté comme une chaîne de bits, car le terme "algorithme" peut être pensé en termes très informels. Dans la thèse de Church-Turing, ils utilisent un concept très rigoureusement défini de ce qu'est un algorithme (et même alors, il y a eu quelques questions sur les mots). Cependant, leur terminologie a obtenu tellement domination qu'il est parfois fait valoir que ces définitions pour des mots comme « algorithme » sont si efficaces que nous les acceptons simplement la définition.
Church-Turing déclare que chaque algorithme peut être implémenté comme un calcul sur une machine de Turing. Étant donné que la description d'une machine de Turing est un ensemble fini de valeurs, il est trivial de voir comment mapper cette description en une séquence de nombres, puis en une séquence de 0 et de 1.
Comme les autres réponses l'ont mentionné, il est trivial de représenter votre exemple d'algorithme en utilisant un codage ASCII ou d'autres codages.
Je pense que la raison pour laquelle votre livre donne cette affirmation comme un fait vient du fait que beaucoup utilisent simplement la thèse de Church-Turing comme base pour leur définition d'un algorithme. Si vous utilisez une telle définition, elle est aussi évidente que "5 est un nombre" car vous l'avez essentiellement définie comme telle.
la source
Cette déclaration est basée sur l'existence de MT universelles . Ce sont essentiellement des MT programmables qui peuvent simuler n'importe quelle autre MT avec au plus une surcharge poly. Par conséquent, votre programme fait simplement partie de l'entrée codée en zéros et en uns.
la source
Eh bien, parlons d'algorithmes qui ne peuvent pas être représentés comme une chaîne de bits finie pour tout type d'encodage.
Permettez-moi de taper un tel algorithme pour vous ... Ah, mais si je le fais, je peux représenter cet algorithme avec l'encodage de mon texte tapé.
Que diriez-vous de représenter mon algorithme en utilisant des «moyens analogiques», disons par la position de quelques pièces sur mon bureau. Bien que la position de ces pièces puisse être modélisée par certains nombres réels (qui dans certains encodages pourraient être impossibles à représenter de manière définitive), cette description entière peut à nouveau être considérée comme une représentation de mon algorithme et peut être à nouveau encodée en une chaîne de bits!
J'espère que ces exemples montrent clairement que si un algorithme ne peut pas être représenté par une chaîne de bits finie, nous n'avons aucun moyen de décrire cet algorithme du tout!
Alors, pourquoi considérerions-nous l'existence de quelque chose dont nous ne pouvons pas parler? Peut-être intéressant pour la philosophie, mais pas pour la science. Par conséquent, nous définissons la notion d' algorithme de telle sorte qu'il puisse être représenté par une chaîne de bits, car alors nous savons au moins que nous pouvons parler de tous les algorithmes.
Bien que la réponse ci-dessus à la question posée, je pense que la confusion au sujet de l'exemple donné est principalement due au fait qu'une représentation n'a besoin que de représenter de manière unique un algorithme. Le mode de représentation n'a pas besoin d'impliquer les calculs réels invoqués par l'algorithme! Ceci est très utile, car cela signifie que nous pouvons également représenter des algorithmes non calculables !
la source
Une autre façon de voir cela est à travers la théorie de l'information. Tous les encodages d'informations / questions significatives / utiles peuvent être transformés en «séquences» binaires.
Une grande partie du champ est consacrée à la question «quelle est la façon de poser le moins de questions en moyenne pour communiquer une information significative? En pratique, cela revient à "quelle est l'approche optimale pour poser le moins de questions oui / non pour comprendre ce qui a été communiqué ou dit?"
la source