Ocena brak

ROZSTRZYGALNOŚĆ

Autor /truchtacz Dodano /13.11.2012

 

ROZSTRZYGALNOŚĆ ang. decidability; fr. decidabilite; nm. Entscheidbarkeit

metod. Własność teorii sformalizowanej: teoria (system twierdzeń) jest rozstrzygalna, gdy istnieje metoda (tzw. efektywna), która pozwala w skończonej liczbie kro­ków stwierdzić, czy dane wyrażenie jest, czy nie jest twierdzeniem tej teorii. Przy­kładem teorii rozstrzygalnej może być —> rachunek zdań, dla którego efektywną metodą rozstrzygania jest metofa zero-je-dynkowa.

Podobnie, przez wskazanie na efektyw­ną metodę {—> algorytm) rozstrzygania, określa się cechę rozstrzygalności w od­niesieniu np. do zbiorów przeliczalnych (tj. równolicznych ze zbiorem liczb naturalnych), do jakiejś klasy pytań, itp.

Podobne prace

Do góry