Tag Archives: computer science

Em 1936, o cientista Alan Turing, em sua publicação “On Computable Numbers, With An Application to Entscheidungsproblem”, descreve o uso de uma máquina de computação universal que poderia pôr fim ao problema de solubilidade em matemática. Como resultado, ele chega à conclusão de que tal máquina não seria capaz de resolver nada corretamente se o resultado de seu trabalho fosse invertido e girado sobre si mesmo. Acontece que é impossível criar um antivírus *ideal*, um configurador de blocos *ideal*, um programa que sugira frases ideais para o seu travamento, etc. Paradoxo!

No entanto, esta máquina de computação universal pode ser usada para implementar qualquer algoritmo, do qual a inteligência britânica se aproveitou, contratando Turing e permitindo a criação de uma máquina “Bombe” para decifrar mensagens alemãs durante a Segunda Guerra Mundial.

A seguir está a modelagem OOP de um computador de fita única na linguagem Dart, com base no documento original.

Uma máquina de Turing consiste em um filme dividido em seções, cada seção contém um símbolo, os símbolos podem ser lidos ou escritos. Exemplo de aula de cinema:

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

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

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

Existe também um “quadrado de digitalização”, que pode mover-se pelo filme, ler ou escrever informações, em linguagem moderna – cabeça magnética. Exemplo de classe de cabeça magnética:

  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; 
  } 
} 

A máquina contém “m-configurações” pelas quais ela pode decidir o que fazer em seguida. Na linguagem moderna – estados e manipuladores de estado. Exemplo de manipulador de estado:

  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(); 

и т.д. 

Depois disso, você precisa criar “configurações”, em linguagem moderna são códigos de operação (opcodes) e seus manipuladores. Códigos de operação de exemplo:

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ão se esqueça de criar um opcode e um manipulador de parada, caso contrário você não será capaz de provar ou deixará de provar (sic!) a resolução do problema.

Agora, usando o padrão “mediador”, conectamos todas as classes da classe Turing Machine, criamos uma instância da classe, gravamos o programa através de um gravador, carregamos a fita e você pode usá-la!

Para mim, pessoalmente, a questão do que era primário permaneceu interessante – criação de uma calculadora universal ou prova do “Entscheidungsproblem” como resultado do qual, como subproduto, apareceu uma calculadora.

Cassetes

Para me divertir, gravei vários programas em fita cassete para minha versão da máquina.

Olá, mundo

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