Pytania otagowane jako normalization

2
Czy można zdecydować równoważność w Systemie F (lub innym typowym rachunku λ)?
Wiem, że nie można zdecydować równoważności dla niepoprawnego rachunku lambda. Cytując Barendregt, HP Rachunek lambda: jego składnia i semantyka. Północna Holandia, Amsterdam (1984). :ββ\beta Jeśli A i B są rozłączne, niepuste zbiory terminów lambda, które są zamknięte na zasadzie równości, to A i B są rekurencyjnie nierozdzielne. Wynika z tego, …

3
Czy możemy udowodnić słabą normalizację dla Systemu F poprzez indukcję na transfinite porządkowej
Słabą normalizację dla prostego rachunku lambda o typie można udowodnić (Turinga) przez indukcję na . Rozszerzony rachunek lambda z rekursorami na liczbach naturalnych (Gentzen) ma słabą strategię normalizacji przez indukcję na ϵ 0 .ω2ω2\omega^2ϵ0ϵ0\epsilon_0 Co z systemem F (lub słabszym)? Czy w tym stylu jest słaby dowód normalizacji? Jeśli nie, …


3
Rachunek konstrukcji: skompresuj wyrażenie do jego najmniejszej postaci
Wiem, że Rachunek Konstrukcji jest silnie normalizujący, co oznacza, że ​​każde wyrażenie ma normalną wartość, która nie może być beta, a jeszcze bardziej zmniejszona eta. W rzeczywistości jest to najbardziej wydajne wyrażenie, które oblicza tę samą wartość, co oryginalne wyrażenie. Ale w niektórych przypadkach normalizacja może zredukować małe wyrażenie do …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.