Máquina de Turing de alfabeto infinito

Uma máquina de Turing com permissão para ler e escrever símbolos de um alfabeto infinito é mais poderosa que uma TM comum (essa é a única diferença, a máquina ainda possui um número finito de estados)?

A intuição não me diz, pois você precisa de um número infinito de estados para diferenciar cada símbolo. Então, acho que alguns dos símbolos ou transições causadas pelos símbolos (ou alguns subconjuntos das transições) devem ser equivalentes. Assim, você pode simular essa máquina com uma TM regular e um subconjunto limitado de tais símbolos ou transições.

Como eu poderia abordar uma prova formal disso?

Não, seria mais poderoso. A função de transição não seria mais finita e isso comprará muito poder.

Com um alfabeto infinito, você pode codificar qualquer item de entrada de um conjunto infinito em um símbolo (embora o conjunto de entrada não possa ser "mais infinito" que o conjunto de alfabeto, por exemplo, o alfabeto provavelmente seria apenas infinitamente contável, portanto, elementos de incontáveis conjuntos como os números reais não podem ser representados em um símbolo). E da mesma forma para a saída.

Assim, você pode criar um TM infinito com dois estados (um inicial, um aceito) com uma única transição que se move para o estado de aceitação e altera o símbolo sob a cabeça da fita de acordo com a função que você está tentando calcular. Esta receita permite calcular qualquer mapeamento entre conjuntos que pode ser colocado em uma correspondência individual com o alfabeto.

Portanto, para evitar que esse tipo de máquina degenerada seja a resposta para tudo, você precisa restringir o que a função de transição pode fazer. Um exemplo óbvio seria exigir que a própria função de transição fosse computável (as funções de transição comuns da TM são trivialmente computáveis, afinal, uma vez que são finitas). Mas você tentaria usar funções computáveis ​​para definir seu modelo de funções computáveis.

A resposta acima está correta, mas há um pouco mais a ser dito sobre alfabetos infinitos e computabilidade.

Uma Máquina de Turing é descrita no WP como na qual todos os conjuntos são finitos. Portanto, a função de transição é necessariamente finita.$M = (Q, \Gamma,b,\Sigma,\delta, q_0, q_f)$

$$\delta: Q / F \times \Gamma \rightarrow Q \times\Gamma \times \{L,R \}$$

Em uma máquina de alfabeto infinito, substituiríamos o alfabeto de entrada por e, portanto, o alfabeto de fita por e a função de transição por obedecendo:$\Sigma$$\Sigma^{inf}$$\Gamma^{inf}$$\delta^{inf}$

$$\delta^{inf}: Q / F \times \Gamma^{inf} \rightarrow Q \times\Gamma^{inf} \times \{L,R \}$$

Então é necessariamente uma função infinita. Conforme observado, se essa função não puder ser computada, o acima não é representável finitamente. Vamos assumir que manteremos (parcial) recursivo, se possível. A questão é se o alfabeto sempre permitirá isso.$\delta^{inf}$$\delta^{inf}$

A questão básica é que um alfabeto finito é apresentado em sua totalidade (para que possamos escolher definir nossas funções recursivamente), mas um alfabeto infinito nunca pode ser apresentado em sua totalidade. Então, qual mecanismo está gerando o alfabeto?

A maneira mais simples de considerar isso é imaginar que exista um alfabeto finito de "núcleo", digamos . Em seguida, gere um idioma . Suponha que corda abaab . Em seguida, defina . Portanto, o alfabeto infinito consiste em conjuntos de strings de concatenados em um único símbolo como .$A=\{a,b\}$$L \subset A^*$ $\in L$$\alpha = <abaab> \in \Gamma^{inf}$$L$$<abaab>$

O alfabeto mais simples é basicamente <1 *> , o idioma regular no qual dois símbolos são distinguidos contando o número de traços verticais em cada símbolo. Isso será computável com um analisador de estado finito (como um LBA, não como um autômato finito). Turing defendeu um alfabeto finito para evitar a aparência de uma operação não finita em uma operação de TM. No entanto, vale a pena notar que as 26 letras do alfabeto inglês não seguem esse padrão de contagem: a letra z não contém 26 pinceladas, pontos ou qualquer outra coisa. Portanto, outros padrões são possíveis com o padrão computacional mais geral que é baseado em uma (re) linguagem recursivamente enumerável .$L$

O problema aqui é que a construção de não será possível, a menos que a definição de seja explicitamente fornecida. Isso ocorre em parte porque a equivalência de redefinições é indecidível e em parte porque, de outro modo, só temos uma amostra finita para trabalhar e não podemos inferir disso. Se tivermos a definição de (e, portanto, ), se for recursivo em$\delta^{inf}$$L$$L$$L$$\Gamma^{inf}$$f$$\Gamma^{inf}$$f$$f$$\delta^{inf}$

$L$

$<n>\in \Gamma^{inf}$$\phi_{n}(n)$$\Gamma^{inf}$$f$$\Gamma^{inf}$$\Delta_2^0$$\delta^{inf}$ não pode ser recursivo.

$S\in\Gamma^{inf}$$S$$f$$\Gamma^{inf}$