Riduzione di TOT a INF

Salve a tutti,
ho sentito che al primo compitino il Degano ha chiesto di dimostrare che TOT si riduce a INF.
Ho provato a dimostrarlo ma inutilmente.... Qualche suggerimento?

Comments

  • MindFlyerMindFlyer Posts: 436
    edited December 2016
    Va bene. C'è una riduzione abbastanza semplice che manda ogni funzione [tex]\varphi[/tex] in una funzione [tex]\varphi'[/tex] che è definita fino a un certo [tex]x[/tex] e non definita da [tex]x[/tex] in poi (col caso degenere [tex]x=\infty[/tex], in cui [tex]\varphi'[/tex] è sempre definita). Ovviamente, se [tex]\varphi[/tex] è totale, dovremo avere [tex]x=\infty[/tex], altrimenti no.

    Come si può fare questa riduzione?
  • mikele_94mikele_94 Posts: 3
    edited December 2016
    Ah ok... credo di aver capito il barbatrucco....

    Costruisco [tex]\varphi_{f(x)}[/tex] in questo modo.
    [tex]\varphi_{f (x)}(y) = \psi (x, y) = \left\{ \begin{array}{ll}
    42 & \mbox{if } \forall z <y. \varphi_x(z) \downarrow\\
    indefinita & \mbox{altrimenti}
    \end{array}
    \right.[/tex]

    In questo modo se [tex]x \in TOT \Rightarrow \varphi_{f(x)}[/tex] calcola la funzione costante [tex]y=42[/tex].
    Perciò [tex]f(x) \in INF[/tex].
    Altrimenti se [tex]x \notin TOT \Rightarrow \exists k \in \mathbb{N}. \varphi_x (k) \uparrow[/tex]. Quindi in questo caso la macchina [tex] \varphi_{f(x)} [/tex]diverge quando ha come input valori maggiori di [tex]k[/tex], dove [tex] k[/tex] è il minimo numero t.c la [tex]\varphi_x(k) \uparrow[/tex].

    Pertanto [tex]dom(\varphi_{f(x)}) = \{0, ..., k \}[/tex], che è finito e quindi [tex]f(x) \notin INF[/tex]

    A grandi linee ti sembra che torni?
Sign In or Register to comment.