Tag Archives: machine

En 1936, le scientifique Alan Turing, dans sa publication « On Computable Numbers, With An Application to Entscheidungsproblem » décrit l’utilisation d’une machine informatique universelle qui pourrait mettre fin au problème de solvabilité en mathématiques. En conséquence, il arrive à la conclusion qu’une telle machine ne serait pas en mesure de résoudre quoi que ce soit correctement si le résultat de son travail était inversé et bouclé sur lui-même. Il s’avère qu’il est impossible de créer un antivirus *idéal*, un poseur de tuiles *idéal*, un programme qui suggère des phrases idéales pour votre crash, etc. Paradoxe !

Cependant, cette machine informatique universelle peut être utilisée pour mettre en œuvre n’importe quel algorithme, dont les services secrets britanniques ont profité en embauchant Turing et en permettant la création d’une machine « Bombe » pour déchiffrer les messages allemands pendant la Seconde Guerre mondiale.

Ce qui suit est la modélisation POO d’un ordinateur à bande unique dans le langage Dart, basée sur le document original.

Une machine de Turing est constituée d’un film divisé en sections, chaque section contient un symbole, les symboles peuvent être lus ou écrits. Exemple de cours de cinéma :

final _map = Map<int, String>(); 

  String read({required int at}) { 
    return _map[at] ?? ""; 
  } 

  void write({required String symbol, required int at}) { 
    _map[at] = symbol; 
  } 
}

Il existe également un “carré de numérisation”, qui permet de se déplacer sur le film, de lire ou d’écrire des informations, en langage moderne – tête magnétique. Exemple de classe de tête magnétique :

  int _index = 0; 
  InfiniteTape _infiniteTape; 
  TapeHead(this._infiniteTape) {} 

  String next() { 
    _index += 1; 
    move(to: _index); 
    final output = read(); 
    return output; 
  } 

  String previous() { 
    _index -= 1; 
    move(to: _index); 
    final output = read(); 
    return output; 
  } 

  void move({required int to}) { 
    this._index = to; 
  } 

  String read() { 
    return _infiniteTape.read(at: this._index); 
  } 

  void write(String symbol) { 
    _infiniteTape.write(symbol: symbol, at: this._index); 
  } 

  int index() { 
    return _index; 
  } 
} 

La machine contient des « m-configurations » grâce auxquelles elle peut décider quoi faire ensuite. En langage moderne – États et gestionnaires d’État. Exemple de gestionnaire d’état :

  FiniteStateControlDelegate? delegate = null; 

  void handle({required String symbol}) { 
    if (symbol == OPCODE_PRINT) { 
      final argument = delegate?.nextSymbol(); 
      print(argument);
    } 
    else if (symbol == OPCODE_GENERATE_RANDOM_NUMBER_FROM_ZERO_TO_AND_WRITE_AFTER) { 
      final to = int.tryParse(delegate!.nextSymbol())!; 
      final value = new Random().nextInt(to); 
      delegate!.nextSymbol(); 
      delegate!.write(value.toString()); 
    } 
    else if (symbol == OPCODE_INPUT_TO_NEXT) { 
      final input = stdin.readLineSync()!; 
      delegate?.nextSymbol(); 
      delegate?.write(input); 
    } 
    else if (symbol == OPCODE_COPY_FROM_TO) { 
      final currentIndex = delegate!.index(); 

и т.д. 

Après cela, vous devez créer des « configurations ». En langage moderne, ce sont des codes d’opération (opcodes) et leurs gestionnaires. Exemples d’opcodes :

const OPCODE_PRINT = "print"; 
const OPCODE_INCREMENT_NEXT = "increment next"; 
const OPCODE_DECREMENT_NEXT = "decrement next"; 
const OPCODE_IF_PREVIOUS_NOT_EQUAL = "if previous not equal"; 
const OPCODE_MOVE_TO_INDEX = "move to index"; 
const OPCODE_COPY_FROM_TO = "copy from index to index"; 
const OPCODE_INPUT_TO_NEXT = "input to next"; 
const OPCODE_GENERATE_RANDOM_NUMBER_FROM_ZERO_TO_AND_WRITE_AFTER = "generate random number from zero to next and write after"; 

N’oubliez pas de créer un opcode et un gestionnaire d’arrêt, sinon vous ne pourrez pas prouver ou échouer (sic !) le problème de résolution.

Maintenant, en utilisant le modèle « médiateur », nous connectons toutes les classes de la classe Turing Machine, créons une instance de la classe, enregistrons le programme via un magnétophone, chargeons la bande et vous pouvez l’utiliser !

Pour moi personnellement, la question de savoir ce qui était primaire restait intéressante : création d’une calculatrice universelle ou preuve du “Entscheidungsproblem” à la suite de laquelle, comme sous-produit, une calculatrice est apparue.

Cassettes

Pour m’amuser, j’ai enregistré plusieurs programmes cassettes pour ma version de la machine.

Bonjour tout le monde

hello world 
stop

0
if previous not equal
16
copy from index to index
1
8
print
?
move to index
0
else
copy from index to index
1
16
print
?
print
Finished!
stop