Discussioni utente:Banus/MdT

Vuoi un input per cui la tua macchina non termina? Infiti 0, seguiti da un 1. --BW Insultami 08:35, Set 26, 2005 (CEST)

Avevo letto male, anche perchè dici che termina immediatamente col blank, ma invece termina immediatamente anche con lo zero. In pratica pensavo fosse

$\delta (s0,b)=\langle b,s1,1\rangle$
$\delta (s0,0)=\langle 0,s0,1\rangle$
$\delta (s0,1)=\langle 1,s2,1\rangle$
$\delta (s1,-)=\langle -,s1,0\rangle$
$\delta (s2,-)=\langle -,s2,0\rangle$

Nel qual caso sarebbe una caso della en:Busy beaver.

Nel caso di una funzione come la tu, sinceramente, non mi viene in mente nulla. Probabilmente perchè usa una logica a tre valori (b, 0, 1). Ci penso su. --BW Insultami 09:02, Set 26, 2005 (CEST)

Ok, credo di aver capito. Il tuo automa a stati finiti praticamente esamina un solo carattere, poi termina. E fin qui, ok. ora, se lo implementi così com'è, ovviamente termina sempre, in quanto non è una macchina ricorsiva: fa sempre una sola iterazione. Ma se lo implementi tramite una macchina ricorsiva, sarebbe possibile trovare un input tale che manda in tilt la macchina ricorsiva. --BW Insultami 09:08, Set 26, 2005 (CEST)

Potresti fare un esempio preciso di macchina ricorsiva che simula questa, con un input che la manda in tilt? Perchè da quanto dici l'implementazione mediante macchina ricorsiva non sarebbe equivalente (non c'è lo stesso comportamento dato lo stesso input, una si ferma sempre l'altra no). Banus 14:43, Set 26, 2005 (CEST)